bingo sort

(algorithm)

Definition: A variant of selection sort which orders items by repeatedly looking through remaining items to find the greatest value and moving all items with that value to their final location. This is more efficient if there are many duplicate values.

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 two passes for each value (not item): one pass to find the next biggest value, and one pass to move every item with that value to its final location. Thus if on average there are more than two items with each value, bingo sort may be faster.

Author: PEB


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black  (paul.black@nist.gov).

Entry modified Tue Jan 9 16:48:24 2001.
HTML page formatted Thu Jan 31 13:48:13 2002.

This page's original URL is http://www.nist.gov/dads/HTML/bingosort.html