PineWikiThe selection sort algorithm sorts by finding the smallest element of an array, then the next smallest element, and so forth, using Theta(n) time at each step where n is the number of elements remaining. It is and example of a DecreaseByConstant algorithm and runs in Theta(n2) in both the worst and the best case.
Like InsertionSort, selection sort can be implemented in-place, with the output array appearing as a prefix of the input array:
{{{SelectionSort(A)
- for i = 1 to length(A):
- best = i for j = i+1 to length(A):
if A[j] < A[best]:
- best = j
- best = i for j = i+1 to length(A):
}}}
Selection sort is more complicated than InsertionSort, has a slightly larger constant, is no faster asymptotically in the worst case, and is slower in the best case. InsertionSort is almost always a better choice.