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).

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.