6-9장 도수 정렬

1. 도수 정렬하기 

 

도수 정렬 (counting sort)

- 요소의 대소 관계를 판단하지 않고 빠르게 정렬

- 데이터의 최솟값과 최댓값을 미리 알고 있는 경우에만 사용 가능

 

1) 도수 분포표 만들기 

2) 누적도수분포표 만들기 

3) 목적 배열 만들기 

4) 배열 복사하기 

 

ex) 10점 만점의 테스트에서 학생 9명의 점수 

배열 a, 요소의 개수 n, 점수의 최댓값 max

 

1.1 도수분포표 만들기 

 

- '각 점수에 해당하는 학생이 몇명인지'

- 배열 f: 도수분포표를 나타내기 위한 배열 

- 먼저 배열 f의 모든 요소의 값을 0으로 초기화 

- 배열 a를 처음부터 스캔하면서 도수분포표 제작

 

for(int i=0; i < n; i++)
	f[a[i]]++;

 

1.2 누적도수분포표 만들기 

 

- '0점부터 점수 n까지 몇 명의 학생이 있는지'

- 배열 f의 두번째 요소부터 바로 앞의 요솟값을 더하는 과정

for(int i=1; i <= max; i++)
	f[i] += f[i-1];

 

 

1.3 목적 배열 만들기 

 

- 배열 a의 각 요솟값과 누적도수분포표 f를 대조하여 정렬을 마친 배열을 만드는 작업 

- 배열 a와 같은 요소의 개수를 갖는 작업용 배열 b 필요 

- 배열 a의 요소를 마지막 위치부터 처음 위치까지 스캔하면서 배열 f와 대조하는 작업 수행

b[--f[a[i]]] = a[i];

 

1) 요소 a[8]

 

 - a[8]의 값은 3

 - f[a[8]]의 값은 5 -> 0~3점 사이에 5명이 있음 

 - 목적 배열 b[4]에 3을 저장 

 - f[3]의 값을 5에서 1만큼 감소 시켜 4로 만듬

 

2) 요소 a[7]

 

- a[7]의 값은 1

- f[1]의 값은 2 -> 0~1점 사이에 2명이 있음

- b[1]에 1을 저장

- f[1]의 값을 2에서 1로 감소시켜 1로 만듬

 

3) 요소 a[6]

 

- a[8]의 값 3을 목적 배열에 넣을 때 f[3]의 값을 1만큼 감소시켜 4로 만들었음

- 미리 값을 감소 시켰기 때문에 중복되는 값인 3을 목적 배열의 4번째 요소(b[3])에 저장 가능 

- 정렬하기 전 배열의 뒤쪽 요소 a[8]이 b[4]에 저장

  앞쪽 요소 a[6]이 b[3]에 저장 

 

1.4 배열 복사하기 

 

- 정렬 결과를 저장한 곳은 작업 배열 b

- 배열 a는 정렬하기 전 상태이므로 배열 b값을 배열 a로 복사해야 함

for(int i=0; i < n; i++)
	a[i]=b[i];

 

- 도수 정렬 프로그램

//도수 정렬 프로그램
#include <stdio.h> 
#include <stdlib.h>

//도수 정렬 함수 (배열의 요솟값은 0이상 max 이하)
void counting (int a[], int n, int max) 
{
	int *f = (int*) calloc(max+1,sizeof(int)); //누적 도수 
	int *b = (int*) calloc(n,sizeof(int)); //작업용 목적 배열
	
	for(int i=0; i <= max; i++) f[i]=0; //배열 f 요소 초기화 
	for(int i=0; i < n; i++) f[a[i]]++; //도수분포표 
	for(int i=1; i <= max;i++)  f[i] +=f[i-1]; //누적도수분포
	for(int i=n-1; i >=0; i--)  b[--f[a[i]]] = a[i]; //목적배열 
	for(int i=0; i<n; i++)  a[i]=b[i]; //배열 복사 
	
	free(b);
	free(f);
}

int main()
{
	int nx;
	const int max=100; //가장 큰값 
	puts("도수 정렬 ");
	printf("요소 개수:");
	
	scanf("%d",&nx);
	int *x = (int*)calloc(nx,sizeof(int));
	printf("0~%d의 정수를 입력하세요.\n",max);
	for(int i=0; i <nx; i++) {
		do {
			printf("x[%d]:",i);
			scanf("%d",&x[i]);
		}while(x[i]<0 || x[i]>max);
	}
	counting(x,nx,max); //배열 x를 도수 정렬
	puts("오름차순으로 정렬했습니다.");
	
	for(int i=0; i < nx; i++)
		printf("x[%d]=%d\n",i,x[i]);
	
	free(x); //배열 x를 해제 
	
	return 0; 
 }