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 ...)
Specialization (... is a kind of me.)
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.
Selection sort illustrated through a Gypsy folk dance. Created at Sapientia University.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 6 April 2018.
HTML page formatted Fri Apr 6 11:20:42 2018.
Cite this as:
Paul E. Black, "selection sort", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 6 April 2018. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/selectionSort.html