Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing two items at a time and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which means the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top (i.e. the beginning) of the list via the swaps. (Another opinion: it gets its name from the way greater elements "bubble" to the end.) Because it only uses comparisons to operate on elements, it is a comparison sort. This is the easiest comparison sort to implement. In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... Swap can refer generically to the exchanging of one thing for another; see also Barter. ... A comparison sort is a particular type of sorting algorithm; a number of well-known algorithms are comparison sorts. ...

A simple way to express bubble sort in pseudocode is as follows: Pseudocode (derived from pseudo and code) is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of programming languages, but omits detailed subroutines, variable declarations or language-specific syntax. ...

 procedure bubbleSort( A : list of sortable items ) defined as: do swapped := false for each i in 0 to length( A ) - 2 do: if A[ i ] > A[ i + 1 ] then swap( A[ i ], A[ i + 1 ] ) swapped := true end if end for while swapped end procedure  

The algorithm can also be expressed as:

 procedure bubbleSort( A : list of sortable items ) defined as: for each i in 1 to length(A) do: for each j in length(A) downto i + 1 do: if A[ j ] < A[ j - 1 ] then swap( A[ j ], A[ j - 1 ] ) end if end for end for end procedure  

This difference between this and the first pseudocode implementation is discussed later in the article.

Analysis

Image File history File links Bubble_sort_animation. ...

Best-case performance

Bubble sort has best-case complexity Ω(n). When a list is already sorted, bubblesort will pass through the list once, and find that it does not need to swap any elements. Thus bubblesort will make only n comparisons and determine that list is completely sorted. It will also use considerably less time than О(n²) if the elements in the unsorted list are not too far from their sorted places. MKH... The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...

Rabbits and turtles

The positions of the elements in bubble sort will play a large part in determining its performance. Large elements at the top of the list do not pose a problem, as they are quickly swapped downwards. Small elements at the bottom, however, as mentioned earlier, move to the top extremely slowly. This has led to these types of elements being named rabbits and turtles, respectively.

Various efforts have been made to eliminate turtles to improve upon the speed of bubble sort. Cocktail sort does pretty well, but it still retains O(n²) worst-case complexity. Comb sort compares elements large gaps apart and can move turtles extremely quickly, before proceeding to smaller and smaller gaps to smooth out the list. Its average speed is comparable to faster algorithms like Quicksort. Cocktail sort, also known as bidirectional bubble sort, cocktail shaker sort, shaker sort, ripple sort, shuttle sort or happy hour sort, is a stable sorting algorithm that varies from bubble sort in that instead of repeatedly passing through the list from top to bottom, it passes alternately from top to... In computer science, comb sort is a relatively simplistic sort algorithm designed by Stephen Lacey and Richard Box, who described it in Byte Magazine in April 1991. ... Quicksort in action on a list of random numbers. ...

Alternative implementations

One way to optimize bubblesort is to note that, after each pass, the largest element will always move down to the bottom. During each comparison, it is clear that the largest element will move downwards. Given a list of size n, the n^th element will be guaranteed to be in its proper place. Thus it suffices to sort the remaining n - 1 elements. Again, after this pass, the n - 1^th element will be in its final place.

In pseudocode, this will cause the following change: Pseudocode (derived from pseudo and code) is a compact and informal high-level description of a computer programming algorithm that uses the structural conventions of programming languages, but omits detailed subroutines, variable declarations or language-specific syntax. ...

 procedure bubbleSort( A : list of sortable items ) defined as: n := length( A ) do swapped := false n := n - 1 for each i in 0 to n do: if A[ i ] > A[ i + 1 ] then swap( A[ i ], A[ i + 1 ] ) swapped := true end if end for while swapped end procedure  

We can then do bubbling passes over increasingly smaller parts of the list. More precisely, instead of doing n² comparisons (and swaps), we can use only n + (n-1) + (n-2) + ... + 1 comparisons. This sums up to n(n + 1) / 2, which is still O(n²), but which can be considerably faster in practice. In mathematics, an arithmetic progression or arithmetic sequence is a sequence of numbers such that the difference of any two successive members of the sequence is a constant. ...

In practice

Although bubble sort is one of the simplest sorting algorithms to understand and implement, its O(n²) complexity means it is far too inefficient for use on lists having more than a few elements. Even among simple O(n²) sorting algorithms, algorithms like insertion sort are usually considerably more efficient. Example of insertion sort sorting a list of random numbers. ...

Due to its simplicity, bubble sort is often used to introduce the concept of an algorithm, or a sorting algorithm, to introductory computer science students. However, some researchers such as Owen Astrachan have gone to great lengths to disparage bubble sort and its continued popularity in computer science education, recommending that it no longer even be taught.[1] Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...

The Jargon file, which famously calls bogosort "the archetypical perversely awful algorithm", also calls bubble sort "the generic bad algorithm".[2] 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", some of which he discusses therein. The Jargon File is a glossary of hacker slang. ... Bogosort is a particularly ineffective sorting algorithm. ... Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ... Cover of books The Art of Computer Programming[1] is a comprehensive monograph written by Donald Knuth which covers many kinds of programming algorithms and their analysis. ...

Bubble sort is asymptotically equivalent in running time to insertion sort in the worst case, but the two algorithms differ greatly in the number of swaps necessary. Experimental results such as those of Astrachan have also shown that insertion sort performs considerably better even on random lists. For these reasons many modern algorithm textbooks avoid using the bubble sort algorithm in favor of insertion sort. In mathematical analysis, and in particular in the analysis of algorithms, to classify the growth of functions one has recourse to asymptotic notations. ... Example of insertion sort sorting a list of random numbers. ...

Bubble sort also interacts poorly with modern CPU hardware. It requires at least twice as many writes as insertion sort, twice as many cache misses, and asymptotically more branch mispredictions. Experiments by Astrachan sorting strings in Java show bubble sort to be roughly 5 times slower than insertion sort and 40% slower than selection sort. In computer architecture, a branch predictor is the part of a processor that determines whether a conditional branch in the instruction flow of a program is likely to be taken or not. ... Example of insertion sort sorting a list of random numbers. ... Selection sort is a sorting algorithm, specifically an in-place comparison sort. ...

Variations

• Odd-even sort is a parallel version of bubble sort, for message passing systems.

Odd-even sort, also known as alternating bubble sort, is a relatively simple sorting algorithm. ... Image File history File links Odd_even_sort_animation. ...

References

• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Pages 106–110 of section 5.2.2: Sorting by Exchanging.
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Problem 2-2, pg.38.
• Sorting in the Presence of Branch Prediction and Caches

Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ... Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...

External links

Wikibooks Algorithm implementation has a page on the topic of

Bubble sort

• Bubble Sort in 20 languages
• Nice graphical visualization of BubbleSort with source code
• Bubble Sort Java Applet
• Bubble Sort Applet
• Bubble Sort Demo
• Bubble Sort Demonstration
• Lafore's Bubble Sort
• Sorting Applets in C++
• C++ Program - Bubble Sort
• C++ Program - Bubble Sort (with an explanation)
• Bubble Sort video and C++ Code
• Practical demonstration
• Analyze Bubble Sort in an online Javascript IDE