선택 정렬

정렬되지 않은 부분에서 가장 작은 값을 찾아 그 부분의 맨 앞자리와 한 번 바꾸는 일을 반복하는 정렬이다. 가장 작은 값을 찾으려고 남은 원소를 전부 비교하므로 비교는 버블 정렬과 같은 n(n-1)/2번이지만, 자리 바꾸기는 한 회차에 최대 한 번이라 전체에서 최대 n-1번이다.