기수 정렬

비교 기반 정렬 알고리즘이 아닌 정렬 방식으로, 데이터를 자리수에 따라 처리하여 정렬한다. 주로 정수나 문자열과 같은 데이터를 정렬하는데 사용되며, 안정 정렬(stable sort)에 속한다. 기수 정렬은 데이터를 가장 낮은 자리수(LSD: Least Significant Digit)부터 처리하거나 가장 높은 자리수(MSD: Most Significant Digit)부터 처리하는 방식으로 동작한다.

장점과 단점

장점

1. 기수 정렬은 비교를 하지 않고 자리수를 기반으로 정렬한다.
2. 데이터의 상대적 순서가 유지된다(안정 정렬)
3. 정렬에 기초한 방법을은 절대 $O(nlogn)$이라는 이론적인 하한선을 깰 수 없는데, 기수 정렬은 시간 복잡도가 $O(kn)$으로 하한선을 깰 수 있는 유일한 기법이다.

단점

1. 범위 제한
   : 기수 정렬은 숫자나 고정된 길이의 문자열에 적합하며, 소수점이나 음수에 대해서는 추가 처리가 필요하다.
2. 메모리 사용
   : 계수 정렬을 사용하므로, 자리수 값의 범위(k)에 따라 추가 메모리를 사용한다.
3. 자리수 기반
   : 데이터의 자리수가 클수록 정렬 시간이 증가한다.

시간 복잡도와 공간 복잡도

시간 복잡도

k개의 자리수를 가지고 있고, n개의 정수를 가지고 있다면 시간 복잡도는 $O(kn)$이 된다. 10진수인 경우 k는 10 이하이다.(k ≤ 10)

공간 복잡도

$O(n + k)$

작동 방식

기수 정렬의 핵심 아이디어는 정렬할 데이터의 각 자리수를 개별적으로 처리하는 것이다.

예를 들어 데이터가 28, 93, 39, 81, 62, 72, 38, 26 이렇게 존재한다고 치면 아래와 같은 과정을 통해 정렬이 진행된다.

각각의 버킷에 먼저 들어간 숫자들은 먼저 나와야 한다. 따라서 버킷은 큐로 구현되어야 한다. 그리고 큐로 구현하기 때문에 요소들의 상대적인 순서가 유지되어 안정적인 정렬이 가능해진다.

위 예제에서 버킷의 갯수는 10개가 사용되었는데 10진법을 정렬하였기 때문이다. 만약 2진법을 정렬하고 싶다면 버킷은 2개만 사용하면 되고, 32비트의 정수의 경우에는 1바이트(8비트)로 4번 나누어 정렬하므로 총 $2^8$= 256개가 된다.

전체 코드

• 큐 구현

  #include <stdio.h>
  #include <stdlib.h>
  
  #define MAX_QUEUE_SIZE 100
  typedef int element;
  typedef struct { // 큐 타입
  	element  data[MAX_QUEUE_SIZE];
  	int  front, rear;
  } QueueType;
  
  // 오류 함수
  void error(char* message)
  {
  	fprintf(stderr, "%s\n", message);
  	exit(1);
  }
  
  // 공백 상태 검출 함수
  void init_queue(QueueType* q)
  {
  	q->front = q->rear = 0;
  }
  
  // 공백 상태 검출 함수
  int is_empty(QueueType* q)
  {
  	return (q->front == q->rear);
  }
  
  // 포화 상태 검출 함수
  int is_full(QueueType* q)
  {
  	return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
  }
  
  // 삽입 함수
  void enqueue(QueueType* q, element item)
  {
  	if (is_full(q))
  		error("큐가 포화상태입니다");
  	q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
  	q->data[q->rear] = item;
  }
  
  // 삭제 함수
  element dequeue(QueueType* q)
  {
  	if (is_empty(q))
  		error("큐가 공백상태입니다");
  	q->front = (q->front + 1) % MAX_QUEUE_SIZE;
  	return q->data[q->front];
  }

• 기수 정렬 구현

  #define BUCKETS 10
  #define DIGIT 2 // 자리수
  
  static int step = 1;
  
  void print_sort(int list[], int n) {
  	for (int i = 0; i < n; i++)
  		printf("%d ", list[i]);
  	printf("\n");
  }
  
  void radix_sort(int list[], int n) {
  	int i, b, d, factor = 1;
  	QueueType queues[BUCKETS]; // 버킷을 정의
  
  	for (b = 0; b < BUCKETS; b++)
  		init_queue(&queues[b]); // 각 버킷들을 초기화
  
  	for (d = 0; d < DIGIT; d++) {
  		for (i = 0; i < n; i++)
  			enqueue(&queues[(list[i] / factor) % 10], list[i]);
  
  		// 버킷에서 꺼내어 list로 합친다.
  		for (b = i = 0; b < BUCKETS; b++)
  			while (!is_empty(&queues[b]))
  				list[i++] = dequeue(&queues[b]);
  		// 자릿수마다 정렬 내용 출력
  		printf("%d단계(%2d의 자리수 정렬): ", step++, factor);
  		print_sort(list, n);
  		factor *= 10; // 다음 자리수로 이동한다.
  	}
  }
  
  // list의 요소 개수
  #define SIZE 8 
  
  int main() {
  	int list[SIZE] = { 28, 93, 39, 81, 62, 72, 38, 26 };
  	
  	radix_sort(list, SIZE);
  
  	return 0;
  }
  

출처
C언어로 쉽게 풀어쓴 자료구조 - 천인구