(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 24 August 2009.
HTML page formatted Tue Dec 6 16:16:32 2011.
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. 24 August 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/selectionSort.html
