비슷한 방법으로 선택 정렬(최솟값 또는 최댓값을 선택하는 방식)이 있습니다.
배열을 정렬하기 위해, 아직 정렬되지 않은 수들 중에서 최솟값을 $n$번 골라 제자리에 놓겠습니다(즉, $k$번째 반복 후에는 $k$번째 위치에 놓습니다). 구현을 간단하게 하기 위해, $k$번째 반복에서는 구간 $[k, n - 1]$에서 최솟값을 찾아 현재의 $k$번째 원소와 자리를 바꾸겠습니다. 그러면 구간 $[0, k]$가 정렬된 상태가 됩니다.
void selection_sort(int *a, int n) {
for (int k = 0; k < n - 1; k++)
for (int j = k + 1; j < n; j++)
if (a[k] > a[j])
swap(a[j], a[k]);
}
정확성과 실행 시간에 대한 증명은 버블 정렬과 유사합니다. $O(n)$번의 반복 각각이 끝날 때마다 $O(n)$ 시간 안에 정렬된 접두사(처음 $k$개의 원소)를 얻으므로, $O(n^2)$번의 연산으로 배열 전체를 정렬하게 됩니다.