(algorithm)
Definition: A sort algorithm that repeatedly looks through remaining items to find the least one and moves it to its final location. The run time is Θ(n²), where n is the number of elements. The number of swaps is O(n).
Generalization (I am a kind of ...)
in-place sort.
Specialization (... is a kind of me.)
bingo sort.
See also strand sort, heapsort, Fisher-Yates shuffle.
Note: Sorting can be done in place by swapping the least remaining item with the item in the next position to be filled. However, this implementation of the algorithm is not stable.
If the (first) least remaining item is inserted, that is, all intervening items moved down (instead of swapping), this algorithm is stable. However, if the items are in an array, rather than, say a linked list, the number of moves is O(n²). The algorithm is then like bubble sort with a more complicated control structure.
Heapsort can be seen as a variant of selection sort in which sorted items are arranged (in a heap) to quickly find the next item.
Author: PEB
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 23 April 2007.
HTML page formatted Mon Apr 23 09:23:15 2007.
Cite this as:
Paul E. Black, "selection sort", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 23 April 2007. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/selectionsrt.html
