Bubble Sort

Bubble Sort is a sorting algorithm that is easy to understand: It makes as many rounds as there are items in the array; in each round, the values of two adjacent items in the array are compared. If the "left" value is larger than the "right" value, the items are swapped. In this manner, in each round the large values go upward, like air bubbles under water (this also why the algorithm bears this name). Despite its simplicity, this algorithm has some serious drawbacks, see the text below the applet.

Update 21.02.2008:
Perhaps surprisingly, also the american president Barack Obama knows the disadvantages of Bubble Sort. For details, take a look at this.

Legend:
pink: greater value in current comparison
red: smaller value in current comparison
blue: the part that is already sorted

The running time of Bubble Sort very high compared to (almost) all other sorting algorithms¹. In Knuth's reference work "The Art of Computer Programming" [1] this algorithm is analyzed in detail. The bottom line is that the only advantages of Bubble Sort are a sticky name and the fact that the analysis of its running time leads to mathematically interesting questions [1, p. 110 and 140]. According to Knuth, the algorithm that is most easily implemented is InsertionSort (and not Bubble Sort), which is also very fast when sorting up to 25 elements, but also that algorithm is very slow on arrays that a few orders of magnitude larger than this. For large arrays, it is advisable to use instead a recursive algorithm like QuickSort. Other options are HeapSort, or MergeSort, which are slightly slower on average, but guarantee fast running time also in the worst-case. Nevertheless, a recent study [2] shows that Bubble Sort still enjoys great popularity, which even exceeds that of the other sorting routines discussed above.

¹ there is also perversely awful sorting routine with even worse running time, namely BogoSort: its expected running time is about (n+1) x n x (n-1) x (n-2) x... x 4 x 3 x 2 x 1, see [3].

Thanks

Update 10.12.2008: Many thanks go out to Tim Tempel who found a bug in the Java applet on this page. That bug is now fixed.

References:

[1] D. E. Knuth. The Art of Computer Programming. Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0.
[2] Owen Astrachan. Bubble Sort: An Archaeological Algorithmic Analysis. 34th ACM Technical Symposium on Computer Science Education, 2003
[3] H. Gruber, M. Holzer und O. Ruepp): "Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms", 4th International Conference on Fun with Algorithms, 2007, Lecture Notes in Computer Science 4475, pp. 183-197

Weblinks on Bubble Sort:

back to the start page