자리를 먼저 정하고 거기 올 값을 고르는 정렬. 첫 번째 자리에 올 값을 찾으려고 전체에서 최솟값을 찾아 가져오고, 두 번째 자리는 나머지에서 최솟값을 찾아 가져온다. 삽입 정렬이 값을 먼저 잡고 자리를 찾는 것과 정반대다.
어떤 입력에도 O(n²)
최선도 평균도 최악도 전부 O(n²)이다. 이미 정렬된 배열을 줘도 이 자리의 최솟값이 무엇인지 알려면 남은 구간을 전부 봐야 하기 때문이다. 버블 정렬이나 삽입 정렬은 정렬된 입력에서 O(n)으로 끝나는데 선택 정렬만 그렇지 못하다. 공간복잡도는 O(1)이라 교환만 하는 제자리 정렬이다.
불안정한 이유
불안정한 이유는 멀리 떨어진 원소와 자리를 바꾸기 때문이다. 최솟값을 찾아 현재 자리로 가져올 때 원래 그 자리에 있던 값이 최솟값이 있던 자리로 날아가는데, 그 사이에 같은 값이 있었다면 순서가 뒤집힌다. 안정 정렬에 그 규칙성을 적어두었다.
가장 적은 교환 횟수
교환 횟수가 최대 n-1번으로 가장 적다. 비교는 많이 하지만 자리를 옮기는 비용이 아주 클 때는 유리할 수 있다. 그런 상황이 흔하지 않아 실무에서 고를 일은 거의 없다.