보통 배열이 정렬되어 있으면 정렬되지 않은 배열보다 더 쉽게 탐색할 수 있습니다. 정렬을 위한 알고리즘 중 선택정렬을 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식의 정렬입니다. 선택 정렬은 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가합니다.
5, 1, 6, 2, 4, 3이란 배열이 주어지고 선택 정렬을 이용하여 정렬해줘야 한다면 다음과 같은 의사코드를 만들 수 있습니다.
버블 정렬과는 다르게 몇 번의 교환을 해주었는지 횟수를 셀 필요가 없습니다. 하지만 이 과정은 훨씬 더 많은 비교가 필요하므로 비용이 많이 듭니다. 원래 배열의 순서와 상관없이, 선택 정렬로 정렬되는 배열은 n-1번의 교환이 필요합니다. n-1번의 교환은 확실히 버블 정렬의 교환 횟수보다는 적습니다. 그러나 한 번의 교환이 일어나기 위해서는 정렬되지 않은 모든 수와 비교가 이루어져야 하므로, n^2번의 비교가 이루어집니다. 선택 정렬은 최선의 경우에도 최악의 경우에서 수행하는 횟수만큼 비교와 교환을 해주어야 합니다.