선택 정렬은 비교와 교환, 두 종류의 단계를 포함한다. 즉, 각 패스스루 내에서 각 값을 현재까지 찾은 최솟값과 비교하고, 최솟값을 올바른 위치에 있는 수와 교환한다.

5개의 원소를 포함하는 배열 예제로 돌아가면, 총 10번의 비교를 해야 했다. 다음 표처럼 나눠서 살펴보자.

▼ 표 5-1

총 4 + 3 + 2 + 1 = 10번의 비교다.

모든 배열 크기에 적용되도록 표현하면 원소 N개가 있을 때 (N - 1) + (N - 2) + (N - 3) … + 1번의 비교다.

이와 달리 교환은 한 패스스루 당 최대 한 번 일어난다. 각 패스스루마다 최솟값이 이미 올바른 위치에 있느냐에 따라 교환을 안 하거나 교환을 한 번 하기 때문이다. 배열이 역순으로 정렬된 최악의 시나리오에서는 버블 정렬과 달리 비교할 때마다 빠짐없이 교환을 한 번 해야 한다.