[정렬 알고리즘] 05 계수 및 기수 정렬(Counting Sort / Radix Sort) 이론 및 구현

1. 계수 및 기수 정렬 개념

1) 계수 정렬

• 각 원소를 사이에 비교하지 않는 정렬이며 안정성(stable)을 가짐
• 임시작업에 사용되는 메모리를 필요로 함 (각 숫자를 counting하여 누적시킬 배열과 정렬된 배열)
• 정렬할 배열의 원소와 숫자를 counting하여 누적시킨 후 그 값들을 정렬된 배열의 인덱스로 사용

 

2) 기수 정렬

• 자리 수를 비교해서 정렬하는 방식
• 가장 낮은 자리 수부터 비교하여 정렬 수행 (비교 연산을 하지 않음)
• 기수정렬이 올바르게 동작되기 위해 각 자리에 사용될 정렬 알고리즘이 안정적이어야 함

---

2. 계수 및 기수 정렬 예제

1) 계수 정렬

 

2) 기수 정렬

---

3. 계수 및 기수 정렬 특성

1) 계수 정렬

① 장점

• $n$이 $k$보다 클 경우 $O(n)$의 시간 복잡도를 가짐
• 평균적인 상황인 퀵 정렬의 시간 복잡도 $O(n \lg n)$보다 빠름(단, 적은 개수의 숫자를 정렬할 때)
• 비교 연산을 하지 않으며 안정성을 가지는 정렬
• 최대 값이 배열의 원소의 개수보다 작은 경우 공간 효율이 뛰어남

② 단점

• 정렬할 때 추가적인 메모리(숫자 개수를 저장할 공간과 결과를 저장할 공간)이 필요로 함
• 가장 큰 숫자에 영향을 받음 -> 즉, 최댓 값에 의해 메모리 공간이 낭비될 수 있음 

 

2) 기수 정렬

① 장점

• 비교 연산을 하지 않으며 안정성을 가지는 정렬
• 시간 복잡도가 $O(dn)$이라는 매우 빠른 정렬이며 이론상 $O(n \lg n)$을 넘을 수 없는 알고리즘

② 단점

• 부동 소수점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없음(데이터 타입이 한정적)
• 제자리 정렬이 아니므로 추가적인 메모리 공간이 필요

---

4. 계수 및 기수 정렬 분석

1) 계수 정렬

▶ Pseudo code(의사코드)

* $A[1, ..., n]$ : 입력 배열, $A.length=n$
* $B[1, ..., n]$ : 정렬된 출력을 저장할 배열
* $C[0, ..., k]$ : 임시 작업 공간, $i(0 \le i \le k)$, $i$값 보다 작거나 같은 숫자들의 개수를 세어 위치시킴
* 8행 for문에서 down to를 사용하는 이유 : 안정성(stable)을 위해(뒤에서 다시 설명)
* 10행에서 C[A[j]]의 값을 감소시키는 이유는 원소들의 값이 서로 같을 수 있으므로

* 시간 복잡도 :

$T(n) = O(k)+O(n)+O(k)+O(n)$ = $2O(k)+2O(n)$

$\therefore O(n+k)$, $n$혹은 $k$라는 뜻으로 $n$이 클지 $k$가 클지 아직 모름

ex) $n >> k$인 경우 $O(n)$ 반대로, $k >> n$인 경우 $O(k)$

※ "down to"

먼저, stable의 의미를 살펴보면

stable이란 정렬되기 전 동일한 값을 가지는 원소들의 순서가 정렬된 후에도 유지되도록 하는 것을 의미

하지만, "up to"를 사용하면 Unstable하여 정렬되지 않음 -> 동일한 값을 가지는 원소들의 수가 뒤바뀜

- 안정성이라는 특성이 중요할 때는 정렬되는 원소에 부속 데이터가 붙어 다닐 때

- 계수 정렬은 종종 기수 정렬의 서브 루틴으로 사용하기 때문

 

2) 기수 정렬

▶ Pseudo code(의사코드)

* $A$ : 정렬할 배열
* $d$ : 자릿수의 개수, ex) $100$이면 $d=3$
* 각 자리가 $0~k-1$범위에 있고, $k$가 지나치게 크지 않다면 계수 정렬이 좋음

ex) 학번일 때 $0~9$ 밖에 없음

* 시간 복잡도 : 
-> $d$자리 숫자가 $n$개일 때 중간 정렬 한 번 걸리는 시간은 $\theta(n+k)$
-> $d$번 반복하므로 총 수행 시간은 $\theta(d(n+k))$

즉, $k$가 작을 때 중간 정렬을 Counting Sort로 사용하는 것이 좋고(외부정렬)

$k$가 클 때 Quick Sort로 사용하는 것이 좋다.(내부 정렬, 메인 메모리가 귀한 상황일 때)

* 외부 정렬과 내부 정렬
① 내부 정렬
- 데이터 양이 적을 때 메인 메모리 내에서 정렬하는 방법
- 속도는 빠르나 정렬할 자료의 양이 많을 경우 부적합
② 외부 정렬
- 대용량 데이터를 몇 개의 서브 파일로 나눠 각각 내부 정렬한 후 테이프나 디스크 내에서 각 서브 파일을 합병하는 방법
- 속도는 느리지만 자료의 양이 많을 경우 효과적

---

5. 계수 및 기수 정렬 시간 복잡도

1) 계수 정렬

• C배열 초기화 과정 : $O(k)$
• C배열 counting 과정 : $O(n)$
• C배열 누적 과정 : $O(k)$
• B배열 초기화 과정 : $O(n)$

$\therefore O(n+k)$

2) 기수 정렬

• d(자릿수)만큼 안정성을 가진 정렬 알고리즘(계수 정렬)을 수행

$\therefore O(dn)$

 

3) 성능 및 평가

	Best	Avg	Worst
계수 정렬	$O(n+k)$	$O(n+k)$	$O(n+k)$
기수 정렬	$O(dn)$	$O(dn)$	$O(dn)$

---

6. 계수 및 기수 정렬 구현(C언어)

#include<stdio.h>
#include<stdlib.h>
#define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))
#define BASE 10		// 10진법 -> Counting Sort할 때 사용


void Radix_Sort(int[], int, int);
int BaseMaxNumber(int[], int, int, int);
void Counting_Sort(int[], int, int, int, int);

int main()
{
	int i;
	int length;
	int arr[10] = { 10, 28, 30, 2, 15, 8, 67, 45, 3, 100, };

	length = sizeof(arr) / sizeof(int);	

	Radix_Sort(arr, length, BASE);

	for (i = 0; i < length; i++)
		printf("%d ", arr[i]);

	system("PAUSE");

	return 0;
}

//Radix_Sort 함수
void Radix_Sort(int arr[], int length, int base) {

	int i, ex, k = 0, max;

	for (i = 0; i < length; i++) {         // 최대 값 구함.   
		if (k < arr[i])
			k = arr[i];
	}

	for (ex = 1; ex <= k; ex *= base) {
		max = BaseMaxNumber(arr, length, ex, base);
		Counting_Sort(arr, max, length, ex, base);
	}
}

// MaxNumber(자리 수 기준으로 최대 값 구하는 함수) --> int형(year)
int BaseMaxNumber(int arr[], int length, int ex, int base) {
	
	int i, max = 0;
	
	for (i = 0; i < length; i++) {
		if (max<(arr[i] / ex) % base) {
			max = arr[i];
		}
	}
	return max;
}

// Countin_Sort 함수
// A : 배열, k : 제일 큰 값(자리 수 기준), n : 배열 원소의 개수, ex : 자리수(1, 10, 100..), base : 진법(10진수)
void Counting_Sort(int A[], int k, int n, int ex, int base) {

	int i, j;
	int *C;
	int *B;

	B = (int*)malloc(sizeof(int)*n);		// 임시 배열 B
	C = (int*)malloc(sizeof(int)*(k + 1));		// 누적 합 배열 C

	for (i = 0; i <= k; i++)			// C배열 0으로 초기화.
		C[i] = 0;
	for (i = 0; i < n; i++)				// C배열에 A배열 자리 수 기준으로 카운트. 
		C[(A[i] / ex) % base]++;
	for (i = 1; i <= k; i++)			// C배열 누적 합.
		C[i] += C[i - 1];
	for (i = n - 1; i >= 0; i--) {			// C배열을 통해 B배열에 A배열의 값 매칭.
		j = (A[i] / ex) % base;
		B[C[j] - 1] = A[i];
		C[(A[i] / ex) % base]--;
	}

	for (i = 0; i < n; i++)				// B배열(정렬된 배열)을 A배열로 옮기기.
		A[i] = B[i];

	free(B);
	free(C);
}