4장에서는 효율성이 O(N²)인 데이터 정렬 알고리즘으로 버블 정렬을 살펴봤다. 이 장에서는 선택 정렬(selection sort)이라는 또 다른 정렬 알고리즘을 자세히 알아보고 버블 정렬과 효율성을 비교해 보겠다.

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

1. 배열의 각 셀을 왼쪽부터 오른쪽 방향으로 확인하면서 어떤 값이 최솟값인지 결정한다. 한 셀씩 이동하면서 현재까지 가장 작은 값을 기록한다(실제로는 그 인덱스를 변수에 저장한다). 변수에 들어 있는 값보다 작은 값이 들어 있는 셀을 만나면 변수가 새 인덱스를 가리키도록 값을 대체한다. 그림으로 살펴보자.

▲ 그림 5-1