[Algorithm] Radix Sort

💡 동작원리

이 글에서는 Radix Sort(기수정렬)에 대해 다뤄보려고 한다. Radix Sort의 원리는 데이터의 낮은 자리수를 이용하여 정렬하는 것이다. Radix Sort는 다른 원소들과 비교 연산을 하지 않아 정렬 속도가 굉장히 빠르다. 그러나 정렬과정에 추가 메모리가 필요하다.

먼저, Radix Sort를 실행하는데에는 추가 메모리인 0 ~ 9까지의 Backet이 필요하다. 이 Backet은 Queue(큐)가 배열을 이용해 연속적으로 할당이 된 자료구조를 가지고 있다.

정렬할 데이터의 값이 {121, 1, 432, 423, 564, 44, 778, 57, 168, 92}이라고 하자. 이제 이 값들의 일의 자리 수에 맞게 Backet에 넣어보자.

위 그림처럼 된다. 이제 이것을 다시 배열에 넣으면, {121, 1, 432, 92, 423, 564, 44, 57, 778, 168}이 된다. 이번에는 십의 자리 수에 맞게 Backet에 넣어보자.

위 그림처럼 된다. 이제 이것을 다시 배열에 넣으면, {1, 121, 423, 432, 44, 564, 168, 57, 778, 92}이 된다. 이번에는 백의 자리 수에 맞게 Backet에 넣어보자.

위 그림처럼 된다. 이제 이것을 다시 배열에 넣으면, {1, 44, 57, 92, 121, 168, 423, 432, 564, 778}이 된다. 배열을 살펴보면 정렬이 끝났다. 이것이 Radix Sort이다. 배열의 데이터 중 가장 큰 자릿수만큼 위 방법을 시행해주면 배열의 모든 데이터의 정렬이 끝난다.

💻 코드

void Radix_Sort(){
	int Max_Value = 0;
	for(int i = 0; i < N; i++){ if(Max_Value < Arr[i]) Max_Value = Arr[i]; }

	int Radix;
	for(Radix = 1; Radix < Max_Value; Radix *= 10){}
	
	for (int i = 1; i <= Radix; i = i * 10){
		for (int j = 0; j < N; j++){
			int Temp = (Arr[j] / i) % 10;
			Backet[Temp].push(Arr[j]);
		}
 
		int Idx = 0;
		for (int j = 0; j < 10; j++){
			while (!Backet[j].empty()){
				Arr[Idx] = Backet[j].front();
				Backet[j].pop();
				Idx++;
			}
		}
	}
}

위 코드는 Radix Sort의 간단한 코드이다. 우선 정렬할 배열에서 가장 큰 값을 찾는다. 그리고 가장 큰 값의 자릿수를 구하여, Backet을 이용해 배열을 정렬해야하는지를 찾는다. 그리고 💡 동작원리에서 설명한 것 처럼, Backet에 자릿 수를 참고하여 넣는다. X자릿수의 값을 구하는 코드는 (원소 / X) % 10을 하면 된다(이유는 계산해보길..). 그리고 다시 Backet에서 수를 빼면서 배열에 순서대로 저장한다. 이를 최대값의 자릿수만큼 반복하여 배열을 정렬한다.

⏱ 시간복잡도

Radix Sort의 시간복잡도는 $O(dN)$이다. 빅오 표기법에 의해 $O(N)$이다. 하지만, 단점으로 Backet으로 사용할 Queue로 이루어진 배열을 선언해주어야 하기 때문에 그만큼 추가 메모리가 든다.

$O(dN) = O(N)$