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()
T-hawk|14 years ago
When a swap costs the same as a compare, bubble sort is as fast as the other N^2 sorts.
thedufer|14 years ago
alttag|14 years ago
A minor tweak is (changed lines marked with #):
alttag|14 years ago