Page 271 - Do it! 자료구조와 함께 배우는 알고리즘(C 언어, 3쇄)

fsort 함수는 배열의 모든 요솟값이 0 이상 max 이하임을 전제로 배열 a에 대해서 도수 정렬

을 수행합니다. 이 프로그램은 키보드로 입력하는 값을 0 이상 max 이하의 값으로 제한합니다.

fsort 함수는 정렬을 위한 작업용 배열 f와 b를 만듭니다. 앞에서 공부한 대로 배열 f는 도수분
포와 누적도수를 넣는 배열이고 배열 b는 정렬한 배열을 임시로 저장하는 배열입니다.

배열 f는 인덱스로 0 ~ max가 필요하므로 총 요소의 개수는 max + 1입니다. 또 배열 b는 정렬 결과를 임시로 저장하는
배열이므로 요소의 개수는 배열 a와 같습니다(n).

프로그램에서 구현한 함수는 총 4단계의 for문을 거칩니다. 첫 번째 for문부터 네 번째 for문
은 도수분포표 만들기, 누적도수분포표 만들기, 목적 배열 만들기, 배열 복사하기의 4단계(지
금까지 공부한 내용)를 의미합니다. 사실 이 for문은 생략할 수 있습니다. calloc 함수가 동적으

로 확보하는 메모리의 모든 값은 0으로 초기화되기 때문입니다.
0단계의 for문은 도수분포와 누적도수분포를 넣어두는 배열 f를 0으로 초기화합니다.

도수 정렬 알고리즘은 데이터의 비교, 교환 작업이 필요 없어 매우 빠릅니다. 단일 for문만을
사용하며 재귀 호출, 이중 for문이 없어 아주 효율적인 알고리즘입니다. 하지만 도수분포표가

필요하기 때문에 데이터의 최솟값과 최댓값을 미리 알고 있는 경우에만 사용할 수 있습니다.
도수 정렬 알고리즘을 구현한 fsort 함수는 배열 a에 저장하는 값을 0 이상 max 이하로 가정합니다. 이렇게 범위를 양수
로 제한하지 않고 정렬하는 프로그램은 연습문제 Q24를 통해 연습하세요.

각 단계(for문)에서 배열 요소를 건너뛰지 않고 순서대로 스캔하기 때문에 같은 값에 대해서
순서가 바뀌는 일이 없어 이 정렬 알고리즘은 안정적이라고 할 수 있습니다. 그러나 3단계(목
적 배열 만들기)에서 배열 a를 스캔할 때 마지막 위치부터가 아닌 처음부터 스캔을 하면 안정적

이지 않습니다. 처음부터 스캔하면 안정적이지 않은 이유를 앞에서 봤던 그림을 이용해 설명
하겠습니다. 그림 6-41과 그림 6-42의 실행 순서가 거꾸로 바뀌면 원래 배열(a)에서 처음에
위치한 값인 3이 a[4]에 저장되고 마지막에 위치한 값인 3이 a[3]에 저장됩니다. 즉, 순서가

반대로 바뀝니다.

연습 Q23 도수 정렬의 각 단계(for문)에서 배열 a, b, f의 요솟값의 변화를 출력하는 프로그램을 작
문제 성하세요.

Q24 요솟값의 범위가 min 이상 max 이하이고 요소의 개수가 n개인 배열 a를 도수 정렬하는
함수를 작성하세요.

void fsort2(int a[], int n, int min, int max);

06•정렬 271