Hacker News Reader

Comment by rafedb | Hacker News Reader

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!

View on HN

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()

Neat. I came back 5 hours later, and the change was live. Thanks. (I was going to submit a change via Git when I got home, but you beat me to it!)

Reply on news.ycombinator.com