(algorithm)
Definition: A sort algorithm that repeatedly searches 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 Black.
Entry modified 2 March 2015.
HTML page formatted Mon Mar 2 16:13:48 2015.
Cite this as:
Paul E. Black, "selection sort", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 2 March 2015. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/selectionSort.html