3 ms·
Yay. 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
by scotty79 15y ago
Yay. 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 < size) || VA.gt(y1, y2)
if VA.lt(y, y1)
VA.swap(y, y1)
y = y1
else
break
else
if VA.lt(y, y2)
VA.swap(y, y2)
y = y2
else
break
pull_up = (y) ->
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)
- scotty79 15y agoYou can also build the heap from the bottom up and change fix_heap a little which altogether is faster and simpler (thanks wiki): fix_heap = (y, size) -> loop y1 = 2*y+1 if y1 >= size then break if y1 + 1 < size && VA.gt(y1 + 1, y1) y1++ if VA.lt(y, y1) VA.swap(y, y1) y = y1 else break for x in [VA.length >> 1 ... -1] by -1 fix_heap(x, VA.length) for x in [VA.length-1 ... 0] by -1 VA.swap(x, 0) fix_heap(0, x)
- thedufer 15y agoI put this implementation in as a prewritten sort. Thanks!