The 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(n²) 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
    swap A[i] and A[best]

}}}

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.

CategoryAlgorithmNotes