(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
animation of many sorting algorithms; animation (Java).
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 E. Black.
Entry modified 17 December 2007.
HTML page formatted Mon Dec 17 10:42:48 2007.
Cite this as:
Paul E. Black, "bubble sort", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 17 December 2007. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/bubblesort.html
