알고리즘(6) - 특수 정렬(계수 정렬, 기수 정렬)

특수 정렬

---

지금까지 봐온 정렬들은 모두 원소끼리 비교해서 정렬하는 비교 정렬 comparison sort이었다. 이 비교 정렬은 최악의 경우, 아무리 빨라도 수행시간이 Θ(nlogn)이다. Ω(nlogn)이라고도 할 수 있다. 다시 말해, '하한'이 존재한다.

 

그러나 원소들이 특수한 성질을 만족하면 다른 기법으로 O(n) 정렬이 가능하다.

• 계수 정렬 Counting Sort
• 기수 정렬 Radix Sort

 

계수 정렬 counting sort

---

원소들의 값이 모두 O(n) 범위에 있을 때 사용가능하다. 또는 -O(n)~O(n) 범위에 있을 때도 가능하다.

이를 전제로 하는 과정은 다음과 같다.

1. 배열 A[1~n]의 원소들이 k(상수)를 넘지 않는 자연수인 경우, 배열에서 1에서 k까지 자연수가 몇 번씩 나타나는지 센다. 
2. 각 원소가 몇 번째에 놓이면 되는지 계산한다.

countingSort(A[],B[],n)
{
	for i ← 1 to k
		C[i] ← 0;
	for j ← 1 to n
		C[A[j]]++;
			▷ 이 지점에서 C[i] : 값이 i인 원소의 총 수
	for i ← 2 to k
		C[i] ← C[i] + C[i-1];
	▷ 이 지점에서 C[i] : i 보다 작거나 같은 원소의 총 수
	for j ← n downto 1 {
		B[C[A[j]]] ← A[j];
		C[A[j]]--;
	}
}

계수정렬을 코드로 구현하면 위와 같은 형식이 된다. 참고로 A: 입력배열, B:정렬결과, n: 입력크기를 나타낸다. 자, 그렇다면 이를 실행했을 때 어떠한 방식으로 구현되는가?

A와 B, C배열에서 일어나는 일

주어진 배열 A[1,2,1,1,3,3]이 있다.

우리는 아까 배열의 원소가 상수 k를 넘지 않는다고 가정했다.

k=3이고, 배열A의 원소들은 1~3의 값을 지니고 있다. 

여기서, 배열C에 같은 원소값의 총 수를 계산해 넣는다. 값이 1인 원소는 총 3개, 2인 원소는 1개, 3인 원소는 2개이므로 C는 3,1,2의 원소값을 갖는다.

그러나 C에서 C[i]보다 작거나 같은 원소의 총수로 다시 구할 필요가 있다.

 

C= {3, 4, 6}

 

왜 이렇게 하는가? 이 배열은 현재 숫자 앞의 갯수 + 현재 숫자다.이는 즉슨, 현재 원소값이 정렬된 배열에서 어느 위치에 있어야 하는지를 알려준다.

원소값이 1인 원소는 3개다. 따라서 0번부터 {1,1,1}로 배치한다. 원소값 2는 하나지만 count 배열에서 4이다. 따라서 원소 1 다음으로 와야 한다. {1,1,1,2} 이렇게 말이다. 원소 3은 2개다. 4번 위치까지 차 있으므로 5,6번에 위치시킨다.

그렇다면, {1,1,1,2,3,3} 이 정렬이 완성된다.

 

이 모든 과정을 거쳤을 때 정렬 수행시간을 나타내면,

Θ(n) (단, k = O(n) 인 경우에 한함)

 

 

기수 정렬 radix sort

---

원소값이 모두 k 자릿수 이하의 자연수인 특수한 경우에 사용할 수 있는 정렬방법이다. 참고로, 자연수가 아닌 알파벳인 경우에도 해당된다.

1. 가장 낮은 1의 자릿수만 가지고 모든 수를 정렬한다.
2. 그 다음으로 낮은 10의 자릿수만으로 정렬한다.
3. 이 과정을 마지막 자릿수까지 반복한다.

radixSort(A[ ], k)
▷ 원소들이 각각 최대 k 자리수인 A[1…n]을 정렬한다
▷ 가장 낮은 자리수를 1번째 자리수라 한다
{
for i ← 1 to k
i 번째 자리수에 대해 A[1…n] 을 안정 정렬한다;
}

안정 정렬은 같은 값을 가진 원소들 간에 정렬 후에도 원래 수서가 유지되도록 하는 정렬을 의미한다.

 

기수 정렬의 예

1의 자릿수부터 모든 수를 정렬한다. 이렇게 했을 때 수행시간은, O(n)이다.

 

이 두 알고리즘은 원소의 비교를 하지 않으므로 선형시간 정렬이 가능하다.