Seite auf deutsch

# 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^{1}.
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.

^{1} 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