빅 오는 훌륭한 도구이지만 유일한 도구는 아니다. 빅 오 표기법에서는 한 알고리즘이 다른 알고리즘보다 훨씬 빠른 경우에도 두 경쟁 알고리즘을 정확히 똑같은 방식으로 표현하기도 한다.

5-1 선택정렬

선택 정렬은 다음과 같은 단계를 따른다

1. 배열의 각 셀을 왼쪽부터 오른쪽 방향으로 확인하면서 어떤 값이 최솟값인지 결정하고 한 셀씩 이동하면서 현재까지 가장 작은 값을 기록한다.
2. 최솟값에 어느 인덱스에 들어 있는지 알았으므로 그 인덱스의 값과 패스스루를 처음 시작했을 때의 값을 교환한다. 첫 번째 패스스루의 시작 인덱스는 0이고, 두 번째 패스스루의 시작 인덱스는 1일 것이다.
3. 매 패스스루는 1, 2 단계로 이뤄진다. 배열 끝에서 시작하는 패스스루에 도달할 때까지 패스스루를 반복한다.

5-2 선택 정렬 실제로 해보기

배열 [4, 2, 7, 1, 3]을 예제로 선택 정렬을 해보자.

첫 번째 패스스루를 시작하며 인덱스 0에 들어있는 값 4을 확인하고 하나밖에 확인 안 했으니 당연히 이 값이 최솟값이다. 이 인덱스를 변수에 저장한다.

1. 현 최솟값인 4와 2를 비교한다. 2가 4보다 작으므로 2가 최솟값이 된다.
2. 현재 최솟값인 2와 7을 비교한다. 여전히 2가 최솟값이다.
3. 현재 최솟값인 2와 1을 비교한다. 1이 더 작으므로 1이 최솟값이 된다.
4. 현재 최솟값인 1과 3을 비교한다. 배열의 끝에 도달했으므로 전체 배열의 최솟값이 1로 결정됐다.
5. 최솟값 1을 패스스루를 시작한 인덱스 0의 값과 교환한다. 1은 이제 올바른 위치에 있게된다. [1, 2, 7, 4, 3]
6. 두 번재 패스스루를 시작한다. 인덱스 0은 정렬됐으므로 인덱스 1부터 시작하며, 이 값 즉, 2가 현재 최솟값이 된다. 현재 최솟값인 2와 7을 비교한다. 여전히 2가 최솟값.
7. 현재 최솟값 2와 4를 비교한다. 여전히 2가 최솟값.
8. 현재 최솟값 2와 3을 비교한다. 배열의 끝에 도달했으므로 최솟값이 2로 확정됐다. 최솟값이 이미 올바른 위치에 있으므로 교환하지 않는다. [1, 2, 7, 4, 3]
9. 세 번째 패스스루를 시작한다. 인덱스 0, 1은 정렬됐으므로 인덱스 2부터 시작하며, 이 값 7이 현재 최솟값이 된다. 최솟값인 7과 4를 비교한다. 4가 7보다 작으므로 4가 최솟값이 된다.