00. 정의

  • 기수(radix)란 숫자의 자리수를 의미한다. 예를 들어 숫자 42는 4(자리수)와 2(자리수)가 기수가 된다. 기수 정렬은 이러한 자리수의 값에 따라서 정렬해서 이런 이름을 얻게 되었다.
  • 기수 정렬은 다단계 정렬이다. 단계의 수는 데이터의 자리의 수의 개수와 일치한다.

01. 요약

  • 입력 데이터에 대해서 어떤 비교 연산도 실행하지 않고, 데이터를 정렬할 수 있는 색다른 정렬 기법
  • 정렬에 기초한 방법들은 절대 O(nlogn)이라는 이론적인 하한선을 깰 수 없는데 반해, 기수 정렬은 이 하한선을 깰 수 있는 유일한 기법이다.
  • 기수 정렬의 문제점은 추가적인 메모리를 필요로 한다는 것인데, 이를 감안해도 다른 정렬 기법보다 빠르기 때문에 데이터 정렬에 인기 있는 기법이다.
  • 기수 정렬의 단점은 정렬할 수 있는 레코드의 타입이 한정된다는 점이다. 기수 정렬을 사용하려면 레코드의 키들이 동일한 길이를 가지는 숫자나 문자열로 구성되어야 한다.
  • 추가 설명
    • 이때까지의 정렬 방법들은 모두 레코드들을 비교해서 정렬한다. 따라서 비교가 불가능한 레코드들은 정렬할 수 없다. 기수 정렬은 레코드를 비교하지 않고도 정렬하는 방법이다.

02. 원리 (작동 방식)

한 자리수 RadixSort

  • 십진수에서 각 자리수가 0에서 9까지의 값만 가지는 것에 착안하면 다음과 같이 10개의 버킷(bucket)을 만들어서 입력 데이터를 각 자리수의 값에 따라 상자에 넣는다. 각 왼쪽상자부터 순차적으로 버킷 안에 들어있는 숫자를 읽는다. 이런 방식으로 정렬한다.

두 자리수 RadixSort

  • [28, 93, 39, 81, 62, 72, 38, 26]인 경우
  • 0 ~ 99번까지 번호가 매겨진 100개의 버킷을 사용하여 앞에서와 마찬가지로 정렬할 수 있다. 이보다 더 효과적인 방법이 있다. 1의 자리수와 10의 자리수를 따로 사용해 정렬하면 10개의 버킷만 사용해 2자리 정수도 정렬할 수 있다.
  • 낮은 자리수로 정렬한 다음 차츰 높은 자리수로 정렬하면 된다.
    • 높은 자리수부터 하면 [28, 26, 39, 38, 61, 72, 81, 93] ⇒ [61, 81, 72, 93, 26, 28, 38, 39] ⇒ X
  • 각각의 버킷에서 먼저 들어간 숫자들은 먼저 나와야 한다. 따라서 각각의 버킷은 큐로 구현되어야 한다. (그래야 리스트 상의 요소들의 상대적인 순서가 유지된다.)
  • 키가 2진법으로 표현 ⇒ 버킷 2개
  • 키가 알파벳으로 표현 ⇒ 버킷 26개
  • 키가 숫자로 표현 ⇒ 버킷 10개

03. 순서도 (알고리즘)

  • 여기서는 2자리 정수의 정렬에 대해 알아보자!
  1. 낮은 자리수부터 각 버킷(큐)에 순서에 맞게 넣는다.
  2. 각 버킷(큐)에서 추출을 해서 다시 리스트를 만든다.
  3. 높은 자리수로 올라가면서 위의 과정을 반복한다.
  4. 가장 높은 자리수까지 위의 과정을 수행하면 정렬은 끝이난다.
const BUCKETS = 10;
const DIGITS = 2; // 이 부분을 수정하면 더 큰 자리 정수도 정렬 가능

const RadixSort = (array) => {
	const queues = Array.from({length: BUCKETS}, () => []); // 버킷 생성
	const arrLen = array.length;
	let factor = 1;

	for (let i = 0; i < DIGITS; i++) {
		for (let j = 0; j < arrLen; j++) {
			queues[parseInt((array[j] / factor) % 10)].push(array[j]); // 1.
		}

		for (let j = 0, arrIdx = 0; j < BUCKETS; j++) {
			while (queues[j].length) {
				array[arrIdx++] = queues[j].shift(); // 2.
			}
		}

		factor *= 10; // 3.
	}
};

const test = [28, 3, 39, 81, 6, 72, 38, 26, 8, 5];

RadixSort(test);
console.log(test);

04. 특징

  • 장점
    • 다른 정렬 방법에 비하여 비교적 빠른 수행 속도를 가진다. (비교하는 과정이 없으므로)
  • 단점
    • 버킷이라고 하는 추가적인 메모리를 필요로 한다.
    • 레코드의 타입이 한정된다.
    • 실수나 한글, 한자 등으로 이루어진 키값을 기수 정렬하고자 할 경우 매우 많은 버킷이 필요하게 되므로, 기수 정렬의 적용이 불가능 할 수 있다. (다른 정렬 방법들은 모든 종류의 키 형태에 적용 가능하다)

05. 복잡도

  • 시간 복잡도
    • 입력 리스트가 n개의 정수를 가지고 있다고 하면 알고리즘의 내부 루프는 n번 반복될 것이다.
    • 만약 각 정수가 d개의 자리수를 가지고 있다고 하면 외부 루프는 d번 반복된다. (대부분의 d는 4이하라고 한다.)
    • 따라서, T(n) = O(dn)

06. 참고

  • C언어로 쉽게 풀어쓴 자료구조 (천인국, 공용해, 하상호 지음)