[알고리즘] 기수정렬, 계수정렬 Radix, Counting Sort (C++ 구현)

버킷정렬, 기수정렬, 계수정렬은 비교에 기반하지 않는 정렬 방법으로 시간복잡도 O(nlogn)보다 빠르게 구현하고자 제안된 정렬 알고리즘이다. 오늘은 기수정렬과 계수정렬에 대해 알아보고자 한다. 간단하니까 툭툭 치고 넘어간다.

📌 기수정렬 Radix Sort

기수정렬의 핵심은 낮은 자리에서 높은 자리로 기준을 바꾸어 가며 정렬하는 것이다. stable sort가 적용된 대표적인 정렬로 이전의 정렬 순서가 바뀌지 않는다. 실제로 정렬을 한다기보다 자릿수에 맞게 0~9까지의 버킷이 있고 이 버킷에 해당하는 자릿수를 포함한 수를 넣는 방식이다. 자리를 바꿔가며 버킷에 넣는 걸 반복하면 자동적으로 정렬이 되는 원리이다. 이때 버킷은 Queue(큐, First In First Out) 방식을 사용한다. 이때 이전 자리수의 버킷을 0부터 차례대로 읽어나가므로 순서가 지켜져 stable 하다. 어쩌면 stable sorting문제를 해결한 직접적인 방법이라고도 볼 수 있다.

 

아래 { 282, 431, 855, 591, 087, 194 } 수를 오름차순으로 정렬해본다. 

수의 범위에 따라 최고 자릿수를 가지는 수에 맞춰 r 번 반복해 버킷에 넣었다 뺐다 하면된다. 

보라색에 집중하기

vector<int> radixsort(vector<int> L) {
	vector<int> target = L;
	vector<vector<int>> bucket(10);
	
	// 자릿수마다 정렬하는 반복문
	for (int x = 0; x < int(log10(*max_element(L.begin(), L.end()))) + 1; x++) {
		for (auto i : target) { // 모든 원소를 자릿수에 맞게 버킷에 삽입
			int digit = (i % int(pow(10, x + 1))) / int(pow(10, x));
			bucket[digit].push_back(i);
		}
		target.clear();
		for (int b = 0; b < bucket.size(); b++) { // 버킷에 차례로 정렬된 것을 다시 꺼내서 리스트로
			if (bucket[b].size() != 0) {
				target.insert(end(target), begin(bucket[b]), end(bucket[b]));
			}
			bucket[b].clear();
		}
	}
	return target;
}

• <cmath> 라이브러리도 굉장히 편하다.

• 밑이 10인 log는 log10(), 밑이 e인 log는 log() 내장함수를 사용한다. 제곱은 pow(x, y) 잊지 말기

• 교수님이 좋아하셨던 벡터의 신세계를 느꼈다. C언어와 자바의 장점만 모아둔 느낌. 잘쓰면 c++이 정말 편할거 같긴 해..

📌 계수정렬 Counting Sort

범위가 작은 수들을 빠르게 정렬할 수 있는 알고리즘이다. 비교를 사용하지 않으며 마찬가지로 stable 하다. 빠른 정렬이 가능하지만 범위가 작고 수가 빈번하게 나오는 배열에서 효과적이라는 점에서 제한적이다. 범위가 작다는 것은 정렬할 리스트의 (최대값 - 최소값)이 작은 것이다. 계수 정렬에서는 (최대값 - 최소값) 범위 내의 수만큼 항목이 필요하다.

 

1. 리스트에서 각 수가 나온 횟수를 센다 (counting)
2. 1번의 결과를 이용해 각 수보다 작은 수가 몇 개 있는지 센다 (누적합)
3. 2번의 결과를 이용해 특정 수가 시작하는 위치를 알 수 있다 (indexing)

약간 헷갈릴 수 있는데 계수정렬의 핵심은 빈도와 범위이다. 

순서대로 카운팅하고, 누적합을 구해 정렬 리스트 내의 각 숫자의 위치를 알면 끝난다.

vector<int> countsort(vector<int> L) {
	int max = *max_element(begin(L), end(L));
	int min = *min_element(begin(L), end(L));
	vector<int> count(max + 1, 0);
	vector<int> countSum(max + 1, 0);
	vector<int> target(L.size(), 0);

	// a. 수가 나온 횟수 카운트
	for (auto l : L) {
		count[l]++;
	}
	// b. a를 이용해 각 수보다 작은 수가 몇 개 있는지 카운트 (누적합)
	for (int i = min; i < max + 1; i++) {
		if (i < 1) {
			countSum[i] = 0;
		}
		countSum[i] = countSum[i - 1] + count[i - 1];
	}
	// c. b를 이용해 특정 수가 해당하는 위치를 출력가능 (같은 값이 여러 개일 수도 있으니 ++ 연산 추가)
	for (auto l : L) {
		target[countSum[l]] = l;
		countSum[l]++;
	}
	return target;
}

• <algorithm> 라이브러리에 있는 max_element, min_element를 사용하면 vector의 최대, 최소값 구하기가 편함

• for(auto i : v) 알고는 있었지만.. 막상 써보니 파이썬 쓰는 기분이 들어 좋다

📌 시간복잡도

위에서 말했듯이 비교에 기반한 정렬의 시간복잡도는 O(nlogn)으로 이보다 빠르게 동작할 수 없다. 이를 위해 비교하지 않는 정렬인 버킷, 기수, 계수 정렬이 있다. 

 

• 버킷정렬의 시간복잡도 : O(n)

• 기수정렬의 시간복잡도 : O(rn) 
  r은 숫자의 자릿수, n은 정렬될 수를 의미한다. 각 자리수에 맞는 버킷에 삽입하는 것은 O(1) 시간이 들며 n개에 대해 적용하므로 O(n), 자릿수 r번 반복하므로 O(rn)임을 간단하게 알 수 있다.

• 계수정렬의 시간복잡도 : O(n + k)
  각 숫자가 나온 횟수를 세는데 counting table을 다시 읽어 횟수를 하나씩 늘려줘야 하므로 n + k 시간이 든다. 그리고 숫자를 다시 정렬된 리스트에 채워넣는데 O(n) 시간이 걸린다. 총 O(n + k)임을 알 수 있다.

---

📌 정렬알고리즘 비교

정렬 알고리즘	stable sort?	시간 복잡도
선택정렬 (selection sort) 버블정렬 (bubble sort) 삽입정렬 (insertion sort)	stable	O(n^2)
병합정렬 (merge sort)	stable	O(nlogn) 보장
퀵 정렬 (quick sort)	피봇 선택기준에 따라 다름	O(nlogn) ~ O(n^2)
힙 정렬 (heap sort)	unstable	O(nlogn)
버킷정렬 (bucket sort)	stable	O(n)
기수정렬 (radix sort)	stable	O(rn)
계수정렬 (counting sort)	stable	O(n + k)