[자료구조] 기수 정렬 (radix sort)

기수 정렬이란?

처음 이 정렬을 들으면 기수라는 단어가 생소할 겁니다. 사전에서 찾아보면 다음과 같습니다.

십진수에서는 0부터 9까지의 숫자를 각 자릿수에 넣을 수 있습니다. 우리는 이 리스트를 오름차순으로 정렬하고 싶습니다. 그렇다면 각 요소마다 가장 낮은 자릿수에서부터 한 자리씩 정렬하면 어떨까요? 사실 이 한 줄이 바로 기수 정렬의 아이디어입니다.

이 때 가장 낮은 자릿수를 LSD(Least Significant Digit)라 하고, 가장 높은 자릿수를 MSD(Most Significant Digit)라 합니다.

기수 정렬은 입력 데이터에 대해서 어떤 비교 연산도 실행하지 않고 데이터를 정렬하는 방식입니다. 왜 그런지 구현 과정을 보면서 확인해봅시다.

 

기수 정렬 구현

기수 정렬의 핵심은 각 자릿수끼리의 정렬입니다.

 

과정은 아래와 같습니다.

1. 자릿수에 들어갈 수 있는 숫자의 개수만큼 버킷(bucket)을 만듬. 예를 들어, 십진수는 10개의 버킷이 필요
2. 정렬할 리스트를 순차적으로 탐색하면서 각 자릿수의 값에 따라 버킷에 삽입
3. 버킷 안에 들어 있는 숫자를 순차적으로 읽음
4. 모든 자릿수를 정렬할 때까지 1.~3. 반복

 

코드로 구현하면 아래와 같습니다.

void radix_sort(int list[], int n) {
	int factor = 1;
	Queue queues[BUCKETS];

	for(int b = 0; b < BUCKETS; b++) {
		init_queue(&queues[b]);
	}
	
	for(int d = 0; d < DIGITS; d++) {
		for(int i = 0; i < n; i++) {
			enqueue(&queues[(list[i] / factor) % 10], list[i]);
		}

		for(int b = i = 0; b < BUCKETS; b++) {
			while(!is_empty(&queues[b]) {
				list[i++] = dequeue(&queues[b]);
			}
		}
		factor *= 10;
	}
}

 

기수 정렬의 시간 복잡도

$d$의 자릿수를 가진 $n$개의 정수를 가진 리스트라고 가정했을 때, 기수 정렬을 수행하면 $O(dn)$의 시간이 소요됩니다. 하지만 컴퓨터에서 십진수의 자릿수를 표현하는 방법은 구조적으로 한계가 있기 때문에 $O(n)$이라고 봐도 무방합니다.

 

 

[자료구조] 선택 정렬 (selection sort)

[자료구조] 삽입 정렬 (insertion sort)

[자료구조] 버블 정렬 (bubble sort)

[자료구조] 셸 정렬 (shell sort)

[자료구조] 합병 정렬 (merge sort)

[자료구조] 퀵 정렬 (quick sort)

[자료구조] 힙 정렬 (heap sort)