선택 정렬

배열 안의 자료 중 가장 작은 수 (혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬. 선택 정렬은 교환 횟수를 최소화하는 반면 각 자료의 비교하는 횟수는 증가한다.

실행

정렬된 배열

버블 정렬과는 다르게 몇 번의 교환을 해주었는지 셀 필요가 없다. 하지만 이 과정은 우리가 해야 할 비교 횟수보다 훨씬 더 많은 비교가 필요하므로 비용이 많이 든다. 원래 배열의 순서와 상관없이, 선택 정렬로 정렬되는 배열은 n-1번의 교환이 필요하다. n-1 번의 교환은 확실의 정렬의 교환 횟수보다는 적다. 그러나 한버의 교환이 일어나기 위해서는 정렬되지 않은 수의 모든 비교가 이루어져야 하므로, n^2 번의 비교가 이루어 진다. 선택 정렬은 최선의 경우에서 수행하는 횟수만큼 비교와 교환을 해주어야 한다.