Bubble sort is actually extremely useful when temporal locality matters more than absolute sort order.

Example: Games often bubble sort world objects by depth. There is a small performance gain to be had by drawing closer objects first, so that you can depth-cull expensive pixels behind them. Game engines can run several iterations of bubble sort, but stop before sorting the set completely, since the z-buffer will ensure correctness. Over the span of several frames, the incremental bubble sort will achieve a total sort, but the incremental approach bounds cost more tightly. Since the depth of objects only changes relatively when you look around, it's usually a pretty good approximation of "perfect" behavior.

Is this very common? Because that would certainly explain the behavior I see in games like WoW where turning my camera drops the framerate, but once I stop turning the framerate jumps back up to normal. I always assumed this had something to do with loading textures or models or geometry or something, but I was never really satisfied with that.

Your assumption was right. The choice of sort is purely an optimization to allow for fast depth-culling, and shouldn't result in noticeable graphical glitches. However, pipelining textures and models based on viewing angles is common. This is certainly what you are seeing.

I wrote Bubble Sort into a very well known game a few years ago, for the case of sorting tiny numbers of view objects. It simply outperformed other sorts. Other sorts were employed for other cases.

This example is neat. Generalizing it a bit... it seems that if you have to visit data frequently in other processing, and you need it ordered later, or for performance, throwing in a swap while doing the visits may help optimize later steps.

This of course assumes that the swap won't mess up the processing algorithm.

It also is an optimization, so best left for later stages of development.

Anyway, thanks for showing this example - it gives me another trick to try for a couple projects I'm working on. :)

I actually use bubble sort early in development when the items to be sorted are complex. Its inefficiency means that most items will be compared against most other items so this will help catch any problems in the complexity of the items and their ordering.

Far more efficient sorting algorithms do not behave very well if the comparison functions give wrong answers and this can be especially difficult to detect.

The bubble sort then helps with the test suite - you can compare the results from the brute force bubble sort against the optimised sort that your framework/language provides.

If you're worried about an incorrect comparison function, you could implement it two different ways.

You could also directly verify (probabilistically) the properties of a total ordering [1]. If your comparison function is "comp" and returns -1, 0, or 1, the tests might go like this:

  trials = 1000
  while trials > 0:

      a = rand_element()
      b = rand_element()
      c = rand_element()

      aa = comp(a, a)
      ab = comp(a, b)
      ac = comp(a, c)
      ba = comp(b, a)
      bb = comp(b, b)
      bc = comp(b, c)
      ca = comp(c, a)
      cb = comp(c, b)
      cc = comp(c, c)

      #reflexive
      assert(aa == 0)
      assert(bb == 0)
      assert(cc == 0)

      #antisymmetric
      assert(ab == -ba)
      assert(ac == -ca)
      assert(bc == -cb)

      #transitive
      assert((ab != bc) or (ab == ac))
      assert((ac != cb) or (ac == ab))
      assert((ba != ac) or (ba == bc))
      assert((bc != ca) or (bc == ba))
      assert((ca != ab) or (ca == cb))
      assert((cb != ba) or (cb == ca))

      assert((ab != 0) or (ac == bc))
      assert((ac != 0) or (ab == cb))
      assert((ba != 0) or (bc == ac))
      assert((bc != 0) or (ba == ca))
      assert((ca != 0) or (cb == ab))
      assert((cb != 0) or (ca == ba))

      trials -= 1

[1] http://en.wikipedia.org/wiki/Total_order

Usually the data is a combination of externally received information and internal calculations/annotations. I just use copious asserts, and one line:

  assert bubble_sort(data) == sort(data)

Since this always runs during development it will automatically pick up internal and external changes.

What you laid out is explicitly testing everything against everything else and is 100% comprehensive. Bubble sort is less than 100% comprehensive but still gives good coverage, while optimised sorts just mean you get lucky in the face of buggy comparisons.

I have used bubble sort in a commercial program before: there are plenty of embedded microprocessors with a minimal libc that does not include qsort. For sorting a small list (5-20 items) bubble sort is a fine choice because it is dead simple to implement.

I have actually used bubble sort once.

I had a small data set, and, more importantly, I needed a customer who might be a less-than-saavy programmer (VBA) to understand what was going on.

Bubble sort is, if nothing else, simple to understand.

But doesn't VBA have a sort method? I would think a line calling a sort method would be more understandable than a sort you implement.

I deny that. Its may be easy to understand the idea; the code is no more enlightening than any other encoded algorithm. A couple of loops,comparing pairs of objects, triple assignment with a temp - what's that all about? You may be able to explain it/ teach it easier because its smaller, but the code is not transparent.

I'd suggest a recursive algorithm would code up far more transparently. E.g. Sort first half of the list; sort 2nd half of the list; merge the two half-lists. That's obvious at the top level; the details of merge are all that's left to explain. It also demonstrates dissecting a problem into smaller problems, so is a double lesson.