(algorithm)
Definition: A variant of selection sort that orders items by first finding the least value, then repeatedly moving all items with that value to their final location and find the least value for the next pass. This is more efficient than selection sort if there are many duplicate values.
Generalization (I am a kind of ...)
selection sort.
See also counting sort.
Note: To see why it is more efficient, consider one value. Selection sort does one pass through remaining items for each item moved. Bingo sort does one pass for each value (not item) and moves every item with that value to its final location.
The name refers to the exclamation, Bingo!, when an item with the right value is found.
The best case complexity is Θ(n+m²), where n is the number of items and m is the number of unique values. The worst case complexity, which is the same as the average case complexity, is Θ(nm).
Author: PEB
Kenneth A. Berman and Jerome L. Paul, Fundamentals of Sequential and Parallel Algorithms, Sect. 4.6, pages 137-139, PWS Publishing Co., Boston, MA, 1996.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 13 November 2008.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "bingo sort", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 13 November 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/bingosort.html