[C++][구현] 기수 정렬 (Radix Sort)

⭐ 기수정렬 (Radix Sort)

계수정렬(Counting Sort)를 이용한 정렬입니다.

 

기수정렬을 하려면, 자리 수 별로 계수 정렬을 실행하면 되는 정렬 방법입니다.

 

각 자리 수의 값을 기준으로, stable한 계수 정렬을 통하여 정렬해줄 수 있습니다.

 

계수정렬의 자세한 내용은 계수정렬을 클릭하여 확인 해 보시면 좋을 듯 합니다. 

---

 

#include <iostream>
#include <cmath>
using namespace std;

void countingSort(int nums[], int length, int radix) {
	int* SortedArr = new int[length];
	int* count = new int[10] {0, };
	int* acc_count = new int[10] {0, };
	
	int div = pow(10, radix);

	for (int i = 0; i < length; i++) {
		count[nums[i] / div % 10]++;
	}

	int tmp(0);
	for (int i = 0; i < 10; i++) {
		tmp += count[i];
		acc_count[i] = tmp;
		acc_count[i]--; // count 라는 개수에서 인덱스로 바꿔주기 위해서.
	}

	// stable 하게 하기 위해서 역순으로 해줍니다.
	for (int i = length - 1; i >= 0; i--) {
		int idx = acc_count[nums[i] / div % 10]--;
		SortedArr[idx] = nums[i];
	}

	// 정리된 arr를 옮겨줍니다.
	for (int i = 0; i < length; i++) {
		nums[i] = SortedArr[i];
	}
	delete[] count;
	delete[] acc_count;
	delete[] SortedArr;
}


void radixSort(int nums[], int length, int radix) {
	for (int i = 0; i < radix; i++) {
		countingSort(nums, length, i);
	}
}

int main() {
	int nums[7] = { 34, 43, 222, 13, 2, 5, 0};
	
	radixSort(nums, 7, 3);
	for (int i = 0; i < 7; i++) {
		cout << nums[i] << ' ';
	}
}

---

기수 정렬의 시간복잡도는 O(nw)입니다. n는 수의 갯수이고, w은 수의 길이입니다.

 

즉 arr = {0, 11, 22, 33333 } 이라면 수의 갯수(n)는 4개이고, 최대글자길이(w)는 5입니다.