도수 정렬

지난 글 : [알고리즘/Do it 알고리즘] - 힙 정렬

 

도수 정렬 알아보기

지금까지 배운 정렬 알고리즘은 두 요소의 키값을 비교해야 했다. 하지만 오늘 배우는 도수 정렬은 요소를 비교할 필요가 없다. 10점 만점 테스트에서 학생 9명의 점수를 예로 도수 정렬 알고리즘으로 살펴보자. 도수 정렬 알고리즘은 도수분포표 만들기, 누적도수분포표 만들기, 목표 배열 만들기, 배열 복사하기 등 4단계로 이루어진다.

 

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

먼저 배열 a를 바탕으로 '각 점수에 해당하는 학생이 몇 명인지'를 나타내는 도수분포표를 작성한다.

배열 a
5	7	0	2	4	10	3	1	3

도수분포표를 저장하기 위해 배열 f를 사용한다. 먼저 배열 f의 모든 요솟값을 0으로 초기화하고, 배열 a를 처음부터 스캔하며 도수분포표를 만든다. a[0]은 5점이므로 f[5]를 1증가시켜 1로 만든다.

배열 f
0	0	0	0	0	0	0	0	0	0	0
====================================================================================
0	0	0	0	0	1	0	0	0	0	0(변경 후)

a[1]은 7점이므로 f[7]을 1 증가키셔 1로 만든다.

배열 f
0	0	0	0	0	1	0	0	0	0	0
====================================================================================
0	0	0	0	0	1	0	1	0	0	0(변경 후)

이 작업을 배열 마지막 요소까지 반복하면 도수분포표가 완성된다.

배열 f
0	0	0	0	0	1	0	0	0	0	0
====================================================================================
1	1	1	2	1	1	0	1	0	0	1(변경 후)

 

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

이제 '0점부터 n점까지 몇 명의 학생이 있는지' 누적한 값을 나타내는 누적도수분포표를 만들자. 아래는 배열 f의 두 번째 요소부터 바로 앞의 요솟값을 더하는 과정을 나타낸다. 가장 마지막이 누적도수분포표가 완성된 모습이다.

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

1	1	1	2	1	1	0	1	0	0	1(초기값)
=================================================================================================
1	2	1	2	1	1	0	1	0	0	1(for문 1회 실행 후)
================================================================================================
1	2	3	2	1	1	0	1	0	0	1(2회 실행 후)
================================================================================================
1	2	3	5	1	1	0	1	0	0	1(3회 실행 후)
================================================================================================
1	2	3	5	6	1	0	1	0	0	1(4회 실행 후)
================================================================================================
1	2	3	5	6	7	0	1	0	0	1(5회 실행 후)
================================================================================================
1	2	3	5	6	7	7	1	0	0	1(6회 실행 후)
================================================================================================
1	2	3	5	6	7	7	8	0	0	1(7회 실행 후)
================================================================================================
1	2	3	5	6	7	7	8	8	0	1(8회 실행 후)
================================================================================================
1	2	3	5	6	7	7	8	8	8	1(9회 실행 후)
================================================================================================
1	2	3	5	6	7	7	8	8	8	9(10회 실행 후)

 

3단계 : 목표 배열 만들기

각각의 점수를 받은 학생이 몇 번째에 위치하는지 알 수 있기에 이 시점에서 정렬은 거의 완료되었다 볼 수 있다.

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

남은 작업을 배열 a의 각 요솟값과 누적도수분포표 f를 대조해 정렬을 마친 배열을 만드는 일이다. 이 작업을 배열 a와 같은 요솟수를 갖는 작업용 배열 b가 필요하다. 이제 배열 a의 요소를 마지막 요소부터 처음 요소까지 스캔하며 배열 f와 대조하는 작업을 수행한다.

 

1. 요소 a[8]

마지막 요소(a[8])의 값은 3이다. 누적도수를 나타내는 배열(f[3])값이 5이므로 0 ~ 3점 사이에 5명이 있음을 알 수 있다. 그러므로 작업용 목표 배열인 b[4]에 3을 저장한다. 조금 어려우니 풀어보면 아래와 같다.

배열 a
5	7	0	2	4	10	3	1	3
=====================================================================================
배열 f
1	2	3	5	6	7	7	8	8	8	9
=====================================================================================
배열 b
b[0]	b[1]	b[2]	b[3]	b[4]	b[5]	b[6]	b[7]	b[8]

위에 나온 메서드를 적용하면,

b[--f[a[i]]] = a[i];
a[i(8)] = 3
--f[3] = 5 - 1 = 4(--연산자는 f 값을 1 뺀 후에 작업을 수행)
b[4] = 배열 b의 5번째 요소

이므로 b[4]에 3을 저장한다. 이 작업에서 f[3]값을 5에서 1 감소시켜 4로 업데이트 하는 이유는 조금 뒤에 배운다.

 

2. 요소 a[7]

바로 앞의 요소 a[7]값은 1이다. 누적도수를 나타내는 f[1]값(2)은 0 ~ 1점 사이에 2명이 있음을 의미한다. 따라서 작업용 목표 배열 b[1]에 1을 저장한다.

현재 배열 b
b[0]	1	b[2]	b[3]	3	b[5]	b[6]	b[7]	b[8]

 

3. 요소 a[6]

배열 a에서 스캔을 계속한다. 다음에 선택한 a[6]값은 3이다. a[8]에서 3점 학생을 배열 b에 저장하는 과정을 이미 한 번 진행했기에 2번째는 다르게 진행한다. 앞에서 a[8]값(3)을 목표 배열에 넣을 때 f[3]값을 1 감소시켜 4로 업데이트했다는 것을 기억하자. 이렇게 미리 값을 감소시켰기에 중복되는 값인 3을 목표 배열의 4번째 요소(b[3])에 저장할 수 있다. 정렬 전의 배열에서 뒤쪽에 있는 3을 b[4]에 저장하고, 앞쪽에 있는 3을 b[3]에 저장한다. 이 작업을 a[0]까지 진행하면 배열 a의 모든 요소를 배열 b의 알맞은 위치에 저장할 수 있다.

 

4단계 : 배열 복사하기

정렬은 끝났지만 정렬 결과를 저장한 곳은 작업 배열 b다. 배열 a는 정렬하기 전 상태이므로 배열 b값을 배열 a로 복사해야 한다.

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

도수 정렬은 if문 없이 for문만으로 정렬하는 매우 아름다운 알고리즘이라고 한다. 직접 코드로 구현해본 결과 확실히 if문 없이 짜니 너무 좋다. if문이 들어간 알고리즘은 이해하는데에 '이 수식이 뭘 의미하지?', '이 조건문은 왜 필요하지?'와 같은 의문이 들 때가 있었고, 이를 해결하는데 생각보다 힘들었다. 하지만 for문은 목적이 단순하고 명확해서 너무나 이해하기 편했다. 아래는 도수 정렬 프로그램이다.

countingSort 메서드는 배열의 모든 요솟값이 0 이상 max 이하임을 전제로 배열 a에 대해 도수 정렬을 수행한다.

 

countingSort 메서드는 정렬을 위한 작업용 배열 f와 b를 만든다. 위에서 배운 대로 배열 f는 도수분폿값을 넣은 뒤 이를 누적도수로 업데이트해 저장하고, 배열 b는 정렬한 배열을 임시로 저장한다. 배열은 생성될 때 모든 요소를 초깃값 0으로 초기화하므로 배열 f의 모든 요소에 일일이 0을 대입하지 않아도 된다.

 

countingSort 메서드는 총 4단계의 for문을 거친다. 각각의 for문은 도수분포표 만들기, 누적도수분포표 만들기, 목표 배열 만들기, 배열 복사하기의 4단계다.

 

도수 정렬 알고리즘은 데이터를 비교, 교환하는 작업이 필요 없어 매우 빠르고, 다중 for문이 아닌 단순 for문만을 사용하며, 재귀 호출과 2중 for문이 없어 아주 효율적인 알고리즘이다. 하지만 도수분포표가 필요하기에 데이터의 최솟값과 최댓값을 미리 알고 있을 경우에만 사용할 수 있다. 

 

for문의 각 단계에서 배열 요소를 건너뛰지 않고 순서대로 스캔하기에 같은 값의 순서가 바뀌는 일이 없어 이 정렬 알고리즘은 안정적이라 할 수 있다. 다만 3단계(목표 배열 만들기)에서 배열 a를 스캔할 때 마지막부터 하지 않고 처음부터 하면 안정적이지 않게 된다. 그 이유는 3단계의 1, 3번의 실행 순서가 뒤바뀌고, 그 결과 원래 배열 a에서 앞쪽에 위치한 값 3이 a[4]에 저장되고 뒤쪽에 위치한 값 3이 a[3]에 저장된다. 결국 순서가 반대로 바뀐다.

 

찬양하라 도수 정렬!

 

참고 서적 :