6-9. 도수 정렬(Counting Sort)

도수 정렬

• 요소의 대소 관계를 비교할 필요가 없음
• 도수분포표 작성, 누적도수분포표 작성, 목적 배열 만들기, 배열 복사의 4단계로 이루어짐

 

 

 

[10점 만점의 테스트에서 학생 9명의 점수 도수 정렬]

1단계. 도수분포표 만들기

• 학생 점수 배열 a를 바탕으로 '각 점수에 해당하는 학생이 몇 명인지'를 나타내는 도수분포표 작성
• 모든 요소의 값을 초기화한 배열 f에 배열 a를 처음부터 스캔하면서 도수분포표 작성
• 예를 들어, a[0]이 5점이면 f[5]를 1만큼 증가시키고 a[1]이 7점인 경우 f[7]을 1만큼 증가시키는 작업을 반복

 

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

 

 

 

2단계. 누적도수분포표 만들기

• '0점부터 점수 n까지 몇 명의 학생이 있는지' 누적된 값을 나타내는 누적도수분포표 작성
• 예를 들어, f[4]의 값이 6이면 0~4점을 받은 학생이 6명임을 의미

 

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

 

 

 

3단계. 목적 배열 만들기

• 각각의 점수를 받은 학생이 몇 번째에 위치하는지 알 수 있으므로 이 시점에서 정렬은 거의 마침
• 남은 작업은 배열의 각 요솟값과 누적도수분포표 f를 대조해 정렬을 마친 배열을 만드는 작업
• 이 과정에서 배열 a와 같은 요소의 개수를 갖는 작업용 배열 b가 필요
• 배열 a의 요소를 마지막 위치부터 처음 위치까지 스캔하면서 배열 f와 대조하는 작업 수행

 

for(int i = n - 1; i >= 0; i--)
	b[--f[a[i]] = a[i];

 

 

 

4단계. 배열 복사하기

• 작업 배열 b의 값을 배열 a로 복사

 

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

 

 

 

 

 

[실습 코드]