Hacker News Reader

Comment by jc4p | Hacker News Reader

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.

View on HN

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

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

Changed to a darker purple. You're right, it was pretty jarring.

Reply on news.ycombinator.com