What is a bubble sort good for?

Question

Do bubble sorts have any real world use? Every time I see one mentioned, it's always either:

1. A sorting algorithm to learn with.
2. An example of a sorting algorithm not to use.

Solution 1

It depends on the way your data is distributed - if you can make some assumptions.

One of the best links I've found to understand when to use a bubble sort - or some other sort, is this - an animated view on sorting algorithms:

http://www.sorting-algorithms.com/

Solution 2

Bubble sort is (provably) the fastest sort available under a very specific circumstance. It originally became well known primarily because it was one of the first algorithms (of any kind) that was rigorously analyzed, and the proof was found that it was optimal under its limited circumstance.

Consider a file stored on a tape drive, and so little random access memory (or such large keys) that you can only load two records into memory at any given time. Rewinding the tape is slow enough that doing random access within the file is generally impractical -- if possible, you want to process records sequentially, no more than two at a time.

Back when tape drives were common, and machines with only a few thousand (words|bytes) of RAM (of whatever sort) were common, that was sufficiently realistic to be worth studying. That circumstance is now rare, so studying bubble sort makes little sense at all -- but even worse, the circumstance when it's optimal isn't taught anyway, so even when/if the right situation arose, almost nobody would realize it.

As far as being the fastest on an extremely small and/or nearly sorted set of data, while that can cover up the weakness of bubble sort (to at least some degree), an insertion sort will essentially always be better for either/both of those.

Solution 3

It doesn't get used much in the real world. It's a good learning tool because it's easy to understand and fast to implement. It has bad (O(n^2)) worst case and average performance. It has good best case performance when you know the data is almost sorted, but there are plenty of other algorithms that have this property, with better worst and average case performance.

Solution 4

I came across a great use for it in an optimisation anecdote recently. A program needed a set of sprites sorted in depth order each frame. The spites order wouldn't change much between frames, so as an optimisation they were bubble sorted with a single pass each frame. This was done in both directions (top to bottom and bottom to top). So the sprites were always almost sorted with a very efficient O(N) algorithm.

Solution 5

It's probably the fastest for tiny sets.

Speaking of education. A link to the last scene of sorting out sorting, it's amazing. A must-see.

View more solutions