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.

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

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/

Answer 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.

Answer 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.

Answer 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.

Answer 6

It's good for small data sets - which is why some qsort implementations switch to it when the partition size gets small. But insertion sort is still faster, so there's no good reason to use it except as a teaching aid.

Answer 7

we recently used bubblesort in an optimality proof for an algorithm. We had to transform an arbitrary optimal solution represented by a sequence of objects into a solution that was found by our algorithm. Because our algorithm was just "Sort by this criteria", we had to prove that we can sort an optimal solution without making it worse. In this case, bubble sort was a very good algorithm to use, because it has the nice invariant of just swapping two elements that are next to each other and are in the wrong order. Using more complicated algorithms there would have melted brains, I think.

Greetings.

Answer 8

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 9

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 10

Bubble sort is easy to implement and it is fast enough when you have small data sets.

Bubble sort is fast enough when your set is almost sorted (e.g. one or several elements are not in the correct positions), in this case you better to interlace traverses from 0-index to n-index and from n-index to 0-index. Using C++ it can be implemented in the following way:

void bubbleSort(vector<int>& v) { // sort in ascending order
  bool go = true;
  while (go) {
    go = false;
    for (int i = 0; i+1 < v.size(); ++i)
      if (v[i] > v[i+1]) {
         swap(v[i], v[j]);
         go = true;
      }
    for (int i = (int)v.size()-1; i > 0; --i) 
      if (v[i-1] > v[i]) {
         swap(v[i-1], v[i]);
         go = true;
      }
  }
}

It can be good if swap of two adjacent items is chip and swap of arbitrary items is expensive.

Donald Knuth, in his famous "The Art of Computer Programming", concluded that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems".

Since this algorithm is easy to implement it is easy to support, and it is important in real application life cycle to reduce effort for support.

Answer 11

It is the sort I use most often actually. (In our project, we cannot use any external libraries.)

It is useful when I know for sure that data set is really small, so I do not care one bit about speed and want shortest and simplest code.

Bubble is not the lowest you can go. Recently, I was in a situation when I needed to sort exactly three elements. I wrote something like this:

// Use sort of stooge to sort the three elements by cpFirst

SwapElementsIfNeeded(&elementTop, &elementBottom);
SwapElementsIfNeeded(&elementTop, &elementMiddle);
SwapElementsIfNeeded(&elementMiddle, &elementBottom);

*pelement1 = elementTop;
*pelement2 = elementMiddle;
*pelement3 = elementBottom;

Answer 12

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 13

I once used it for a case where the vast majority of the time it would be sorting two items.

The next time I saw that code, someone had replaced it with the library sort. I hope they benchmarked it first!

Answer 14

It's quick and easy to code and (nearly impossible to do wrong). It has it's place if you're not doing heavy lifting and there's no library sorting support.

Answer 15

Oh yes, it is a good selection mechanism. If you find it in code written by someone, you don't hire him.

Answer 16

Mostly nothing. Use QuickSort or SelectionSort instead...!