3.12.1 카운트 정렬

카운트 정렬(counting sort)은 가장 간단하고 효율적인 정렬 방법으로, 미리 정의된 데이터 범위에서만 동작하는 엄격한 요구 사항이 있습니다. 예를 들어 연령대별로 몇 명의 사람이 있는지 정렬한다고 해봅시다. 나이의 범위는 1세에서 130세입니다.

▲ 그림 3-15 카운트 정렬

입력 데이터에서 각 값의 수를 세어 1이 3개, 2가 1개의 형태로 카운트 배열에 저장합니다. 저장된 카운트 배열을 다시 읽어 그 값만큼 차례대로 출력 배열에 저장합니다. 카운트 배열의 0 인덱스는 값이 0이니 넘어가고, 1은 3개니 출력에 0~2까지 3개의 인덱스에 1을 저장하고, 그다음 2를 1개, 4를 2개의 형태로 차례대로 저장합니다.

입력 범위를 알면 O(n + k) 시간에 카운트를 이용해 정렬합니다. 이때 n은 사람 수, k는 최대 연령인 130으로 가정합니다.