What is a bubble sort good for? [closed]

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.

Answer 1

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.

Answer 2

I used to use it in some cases for small N on the TRS-80 Model 1. Using a for loop, one could implement the complete sort on one program line.

Other than that, it is good for teaching, and sometimes for lists that are nearly in sorted order.

Answer 3

I can't resist responding to any remarks on bubble sort by mentioning the faster (seems to be O(nlogn), but this is not really proven) Comb Sort. Note that Comb sort is a bit faster if you use a precomputed table. Comb sort is exactly the same as bubble sort except that it doesn't initially start by swapping adjacent elements. It's almost as easy to implement/understand as bubble sort.

Answer 4

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.

Answer 5

I think it's a good "teaching" algorithm because it's very easy to understand and implement. It may also be useful for small data sets for the same reason (although some of the O(n lg n) algorithms are pretty easy to implement too).

Answer 6

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.