(algorithm)
Definition: Sort by comparing each adjacent pair of items in a list in turn, swapping the items if necessary, and repeating the pass through the list until no swaps are done.
Also known as sinking sort, exchange sort.
Generalization (I am a kind of ...)
in-place sort, stable sort.
See also gnome sort, bidirectional bubble sort.
Note: Complexity is O(n2) for arbitrary data, but approaches Θ(n) if the list is nearly in order at the beginning. Bidirectional bubble sort usually does better since at least one item is moved forward or backward to its place in the list with each pass. Gnome sort optimizes the moving forward and backward instead of blindly looping through all items.
Since at least one item is moved into its final place for each pass, an improvement is to decrement the last position checked on each pass.
The name "sinking sort" comes from elements sinking down to their proper position. Contributed by Ken Tata (Ken.Tata@onsemi.com) 22 December 2000. After LK.
Author: PEB
Bubble sort animated.
Quicksort vs bubble sort race.
Insertion sort vs bubble sort race followed by analysis of bubble sort, insertion sort, and quick sort.
Stooge sort vs bubble sort race.
Bubble sort illustrated through a Hungarian folk dance: Csángó. Created at Sapientia University.
Marvin V. Zelkowitz, Principles of Software Engineering and Design, Prentice-Hall, page 107, 1979.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 7 April 2023.
HTML page formatted Fri Apr 7 09:27:46 2023.
Cite this as:
Paul E. Black, "bubble sort", in
Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 7 April 2023. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/bubblesort.html