Commenting to save for later
Voting the submission up and then going to http://news.ycombinator.com/saved?id=matlaber would do the same without adding a comment to the thread.
Show HN: Write a sort, watch it go
71–80 of 89 posts
Re: Show HN: Write a sort, watch it go
#72Sleep 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 * v
Never heard of this one. It's awesome.
Re: Show HN: Write a sort, watch it go
#73Stooge sort:
stoogesort = (lo, hi) ->
if VA.lt(hi, lo)
VA.swap(lo, hi)
if hi - lo > 1
third = Math.floor((hi - lo + 1)/3)
stoogesort(lo, hi-third)
stoogesort(lo+third, hi)
stoogesort(lo, hi-third)
stoogesort(0, VA.length-1)
Re: Show HN: Write a sort, watch it go
#74Staring at screen looking at how bars shift and swap, I think merge sort is most elegant visually.
Re: Show HN: Write a sort, watch it go
#75Very 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…
1. Requires a bit more work than I have time for right now. I'll keep it in mind. 2. Fantastic idea. This is exactly what I needed when I was struggling to write a quicksort from memory. Its in there now.
I just sent you a pull request that implements 1.
Re: Show HN: Write a sort, watch it go
#76Hash sort is surprisingly fast: for x in [0 ... VA.length] ind = VA.get(x)-1 VA.swap(x, ind + VA.length) for x in [0 ... VA.length] VA.swap(x, x + VA.length)
In 1/2 as many swaps:
for x in [0 ... VA.length]
ind = VA.get(x)-1
while ind != x
VA.swap(x, ind)
ind = VA.get(x)-1Re: Show HN: Write a sort, watch it go
#77This is a good set of sorting visualisations too, presented more compactly (but not customisable): http://www.sorting-algorithms.com/
Re: Show HN: Write a sort, watch it go
#78Earlier quoted context omitted.
That's still a quicksort - it always has n^2 as its worst case I thought? If you pick the wrong pivot each time.
> That's still a quicksort - it always has n^2 as its worst case I thought? If you pick the wrong pivot each time. Pick median of three random elements as pivot; it's hard to pick wrong pivot every time unless your RNG always returns 7.
Why three random elements though? If you expect some structure in the array, then picking pivots based on that structure makes more sense (e.g. first, middle and last for sorted, reverse sorted for partially sorted arrays).
On the other hand, if you are sorting unsanitised input, then random is good, but it should be secure pseudo-random numbers if it's important to your security/performance whilst under attack.
Re: Show HN: Write a sort, watch it go
#79Re: Show HN: Write a sort, watch it go
#80It's fantastic. I don't know CoffeeScript so all I did was compare the pre-written ones to each other and see if they did what I expected them to do, but it's a nice visual representation. The only problem I have with it is that the neon yellow on black with a gray/white background can be pain inducing, especially when moving quickly.
Speaking of pain inducing, I found watching the bubble sort very pain inducing! I've always known it was slow compared to other options, but this make you never want to see the thing mentioned again!
I know Bubble sort is "bad", but there's no reason to make it worse than it needs to be. The current algorithm continues comparing the items that have already "bubbled" (or in this case, "sunk") by iterating the whole length on each pass, rather than shorting the loop to only consider the unsorted portion.
A minor tweak is (changed lines marked with #):
bubbleSort = ->
VA.locals.swapped = true
y = VA.length # grab initial length
while VA.locals.swapped
y-- # shorten sorted portion on each pass
VA.locals.swapped = false
for x in [0...y] # only iterate to y
VA.locals.x = x
if VA.gt(x, x + 1)
VA.swap(x, x + 1)
VA.locals.swapped = true
bubbleSort()