It'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.
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).
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()
I don't like the insertion sort. Couldn't it do a binary search on the sorted part of the list, when it's looking for the place to put the next element?
I coded up the easiest version of each algorithm, rather than the most efficient. (Quicksort uses the first element as a pivot, rather than something more intelligent) Feel free to email me an algorithm if you think it should be there/is better than what I wrote. The pre-written algorithms weren't exactly my focus.
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()
This is exactly what's going on. You can't get a reflow on the page without giving up control, and I didn't want to require people to write asynchronous code to give up control after every swap. So it runs your code and queues up actions, to be played back when its done. This is also why you have to use the methods on VA instead of working directly on the array.
The 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.
There are ways to make the n^2 worst case extraordinarily unlikely, and there is a way to make it impossible (though it is highly technical).
Some others have posted methods (random pivot, median of 3). The gnu libc qsort implementation is a good learning tool (it uses median of 3). I think CLRS has the guaranteed n log n version.
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.
I said this in another comment, but I coded up the simplest version of each algorithm - the quicksort is correct, just not optimal. The focus was on letting people write their own code, not the pre-written algorithms.
sort = (begin, end, bit) ->
i = begin
j = end
mask = 1 << bit
while i < j
while i < j and !(VA.get(i) & mask)
++i
while i < j and (VA.get(j - 1) & mask)
--j
if i < j
VA.swap(i++, --j)
if bit and i > begin
sort(begin, i, bit - 1)
if bit and i < end
sort(i, end, bit - 1)
sort(0, VA.length, 30)
This 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.
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<=mid && mid<=hi
if VA.gt(lo,mid)
VA.insert(mid, lo)
mid++
else
lo++
s(0,VA.length)
Very 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.
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
87 comments
[ 4.9 ms ] story [ 220 ms ] threadWhen a swap costs the same as a compare, bubble sort is as fast as the other N^2 sorts.
A minor tweak is (changed lines marked with #):
Did someone solve the halting problem while I wasn't looking?
Some others have posted methods (random pivot, median of 3). The gnu libc qsort implementation is a good learning tool (it uses median of 3). I think CLRS has the guaranteed n log n version.
Pick median of three random elements as pivot; it's hard to pick wrong pivot every time unless your RNG always returns 7.
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.
VA.swap(left, Math.floor(Math.random() * (right - left + 1)) + left)
I thought it was a bit clearer to understand what it was doing when I stuck
at the very top of your sort function.http://www.youtube.com/watch?v=ywWBy6J5gz8
This allows "algorithms" like this:
Also, that's not going to work quite right - the values are [1..VA.length] (see the bottom of the page), while the indices are [0...VA.length].
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.
Instead of actually doing the operations, your sorting code outputs a list of actions to perform, which is then displayed on the webpage.
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
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.
2. Fantastic idea. This is exactly what I needed when I was struggling to write a quicksort from memory. Its in there now.