선택 정렬은 아직 정렬하지 않은 부분에서 최솟값을 찾아 앞쪽의 확정 위치로 옮기는 정렬이다.
원리
첫 단계에서는 전체 최솟값을, 다음 단계에서는 남은 부분의 최솟값을 고른다. 비교 횟수는 입력의 기존 정렬 정도와 관계없이 대체로 이차 규모이다.
예시
3, 1, 2에서 1을 찾아 첫 원소와 교환하면 1, 3, 2가 된다. 남은 두 원소를 처리하면 정렬이 끝난다.
주의할 점
일반적인 교환 구현은 안정적이지 않다. 교환 횟수는 O(n)으로 적지만 최솟값 탐색의 비교 비용은 O(n²)이므로 큰 입력에서 빠르다고 볼 수 없다.