Hash 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)
That's cheating somehow...
Show HN: Write a sort, watch it go
51–60 of 89 posts
Re: Show HN: Write a sort, watch it go
#52This might be a dumb question, but can you add numbers about the size of the stack to the right-side statistics? I.e. How many variables and calls to functions are stored in memory at at a time. I'm not sure if this possible or relevant to record based on how Javascript engines compile and work, but it would seem interesting to know.
The implementation here is doing tricksie things behind the scenes to make this work without instrumenting the javascript engine.
Instead of actually doing the operations, your sorting code outputs a list of actions to perform, which is then displayed on the webpage.
Re: Show HN: Write a sort, watch it go
#53It'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!
Looks like bubble sort is so slow because this implementation has a very high ratio between the costs of a compare and a swap. A swap involves redrawing large parts of the graphical area, while a compare is fast. Bubble sort makes N^2 swaps, as compared to insertion sort which makes N^2 comparisons but only N swaps.
When a swap costs the same as a compare, bubble sort is as fast as the other N^2 sorts.
Re: Show HN: Write a sort, watch it go
#54The quicksort implementation is incorrect. The code simply picking the left-most element as the pivot, and as a result it becomes pathologically slow for nearly-sorted array -- for example, run bubblesort then quicksort, or run quicksort twice -- not to mention potential stack overflow problem due to O(N) recursive call.
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.
Re: Show HN: Write a sort, watch it go
#55Earlier quoted context omitted.
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!
Looks like bubble sort is so slow because this implementation has a very high ratio between the costs of a compare and a swap. A swap involves redrawing large parts of the graphical area, while a compare is fast. Bubble sort makes N^2 swaps, as compared to insertion sort which makes N^2 comparisons but only N swaps. When a swap costs the same as a compare, bubble sort is as fast as the other N^2 sorts.
Turn off "Quick Compare" to make comparisons take longer if you want a different ratio. By default, it takes about 1/15 as long to compare as swap (I thought the visualization looked better this way).
Re: Show HN: Write a sort, watch it go
#56Yay. 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 ...…
You 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 > 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)Re: Show HN: Write a sort, watch it go
#57I love the stats on the side. Knowing how many comparisons and swaps occur really shows the complexity of the algorithms.
And to segue into my own area of interest with sorting, it would be awesome to see cache and branch behaviour too (though of course this running in the browser, it's not exactly the real behaviour, but still).
Re: Show HN: Write a sort, watch it go
#58This might be a dumb question, but can you add numbers about the size of the stack to the right-side statistics? I.e. How many variables and calls to functions are stored in memory at at a time. I'm not sure if this possible or relevant to record based on how Javascript engines compile and work, but it would seem interesting to know.
The implementation here is doing tricksie things behind the scenes to make this work without instrumenting the javascript engine. Instead of actually doing the operations, your sorting code outputs a list of actions to perform, which is then displayed on the webpage.
Yes; however, at each step I'm already storing the state of VA.locals. If you can show me how I would get this data, I'd be happy to display it.
Re: Show HN: Write a sort, watch it go
#59definitely have the page start with an example.
Makes sense. Starts with a bubble sort now.
Re: Show HN: Write a sort, watch it go
#60How about adding the VA.equals and VA.notequals functions? You've got all the other comparators, but it seems a shame that you don't have these.
I...don't know how I missed them. They're in now.