[deleted]
Show HN: Write a sort, watch it go
41–50 of 89 posts
Re: Show HN: Write a sort, watch it go
#42Merge sort:
s = (lo, hi) ->
if lo==hi
return
if lo+1==hi
if VA.gt(lo,hi)
VA.swap(lo,hi)
return
mid=Math.floor(lo+(hi-lo)/2)
s(lo,mid)
s(mid+1,hi)
mid++
while loRe: Show HN: Write a sort, watch it go
#43Radix-exchange sort: sort = (begin, end, bit) -> i = begin j = end mask = 1 begin sort(begin, i, bit - 1) if bit and i
Neat, I've never actually seen a radix sort before.
I thought it was a bit clearer to understand what it was doing when I stuck
VA.locals.bit = bit
Re: Show HN: Write a sort, watch it go
#44Nice, though I think static visualizations illustrate the examples more quickly and are easier to compare:
http://corte.si/posts/code/visualisingsorting/index.html
I also love Robert Sedgewick's technique of using angle to encode array value. Animated and static examples here:
http://bl.ocks.org/1243323 http://mbostock.github.com/protovis/ex/sort.html
Re: Show HN: Write a sort, watch it go
#45Very neat, but here's a couple of additions I'd like to see:
1. Allow for the array to contain values outside of the range of [1..length]. Ideally, allow for duplicate values as well. Since you control the swap and insert operations, you can maintain two separate sets, one of the actual numbers, and one of the "normalized" values that you display as your graph.
2. Give us an operation to highlight a set of lines and have the highlights persist. I wanted to take mayoff's radix-exchange sort and tweak it to highlight the "working set" that it's currently sorting, but there's no way to do that. I'm thinking here that we just need one function VA.persistHighlight() which takes start and end indices and highlights them, and persists those highlights until a new call to VA.persistHighlight(). The "transient" highlights would be layered on top of the persistent one.
Re: Show HN: Write a sort, watch it go
#46Sleep sort:
pos = [0 ... VA.length]
rpos = [0 ... VA.length]
swap = (i, j) ->
VA.swap i, j
tmp = rpos[j]; rpos[j] = rpos[i]; rpos[i] = tmp
pos[rpos[i]] = i; pos[rpos[j]] = j
j = 0
for i in [0 ... VA.length]
v = VA.get(i)
do (v, i) ->
setTimeout ->
# Move the element that was originally in position i to position j
swap pos[i], j++
VA.play()
, 100 * vRe: Show HN: Write a sort, watch it go
#47Merge sort: s = (lo, hi) -> if lo==hi return if lo+1==hi if VA.gt(lo,hi) VA.swap(lo,hi) return mid=Math.floor(lo+(hi-lo)/2) s(lo,mid) s(mid+1,hi) mid++ while lo
Merge sort w/o using insert (and probably with some bugs...):
tmp = VA.length
merge = (start1, start2, end2) ->
out = start1
end1 = start2 - 1
for x in [tmp+out .. tmp+end2]
if start1
if (right - left) == 1
if VA.gt(left, right)
VA.swap(left, right)
else if (right - left) == 0
/* do nothing */
else
split = Math.floor((right-left)/2) + left;
mergesort(left, split - 1)
mergesort(split, right)
merge(left, split, right)
mergesort(0, VA.length - 1)Re: Show HN: Write a sort, watch it go
#48definitely have the page start with an example.
Re: Show HN: Write a sort, watch it go
#49Needs a shuffle() function - can't bogosort without it.
Bogo
shuffle = ->
for x in [0..VA.length]
VA.swap x, Math.floor(Math.random()*VA.length)
sort = ->
VA.play()
if !checkSorted()
shuffle()
setTimeout(sort, 10)
checkSorted = ->
for x in [0..VA.length-1]
if VA.gte(x, x+1)
return false
return true
sort()Re: Show HN: Write a sort, watch it go
#50Yay. My first program in CoffeScript. It was fun to implement algorithm of which I only vaguely remembered how it worked. Details bit me few times before I got it working and right.
Heapsort:
fix_heap = (y, size) ->
loop
y1 = 2*y+1
y2 = 2*y+2
if y1 >= size then break
if !(y2
loop
y0 = (y-1) >> 1
if y == 0 || VA.lt(y, y0) then break
VA.swap(y0, y)
y = y0
for x in [1 ... VA.length]
pull_up(x)
for x in [VA.length-1 ... 0] by -1
VA.swap(x, 0)
fix_heap(0, x)