[기수 정렬] 숫자의 자릿수를 활용한 빠른 비비교 정렬 알고리즘

728x90

기수 정렬(Radix Sort) 

기수 정렬(Radix Sort)은 데이터를 정렬할 때 숫자의 자릿수(또는 문자열의 위치)를 기준으로 정렬하는 비교하지 않는(non-comparison based) 정렬 알고리즘입니다. 버블 정렬이나 퀵 정렬처럼 값을 비교하지 않고, 숫자나 문자열의 각 자리를 기준으로 여러 번 분류하여 정렬합니다.
정수나 고정 길이 문자열과 같이 구조가 명확한 데이터에서 매우 빠르게 동작할 수 있으며, 특히 비교 기반 정렬의 이론적 하한인 O(n log n)을 우회하여 O(nk)의 성능을 달성할 수 있습니다.

단점으로는 비교 기반이 아니므로 모든 데이터에 적용할 수는 없으며, 자릿수를 기준으로 반복 작업이 필요하기 때문에 메모리 사용량도 상대적으로 높을 수 있습니다.

 

---

1.  기수 정렬이란?

Radix Sort  (출처 : https://herong.tistory.com/m/190?category=818669)

 

기수 정렬은 숫자의 자릿수나 문자열의 인덱스를 기준으로 여러 번 정렬을 수행하여 전체를 정렬하는 알고리즘입니다.
각 자릿수 정렬은 보통 계수 정렬(Counting Sort) 같은 안정 정렬을 활용합니다.

작동 방식 (LSD 기준)

LSD: Least Significant Digit (가장 낮은 자리수부터 정렬)

1. 가장 낮은 자릿수부터 시작해 데이터를 정렬합니다.
2. 그 다음 높은 자릿수를 기준으로 다시 정렬합니다.
3. 가장 높은 자리까지 반복 정렬하면 전체 정렬이 완료됩니다.

장점

• 비교하지 않음 → 비교 기반 정렬보다 빠를 수 있음
• 정수 기반 데이터에 매우 유리
• 정렬 안정성 유지 가능
• O(n log n)보다 빠른 O(nk) 시간 복잡도 가능

단점

• 범용적이지 않음 (문자열/정수 등 구조화된 데이터만)
• 자릿수에 따라 반복 횟수 많아질 수 있음
• 추가 메모리 사용 (계수 정렬 기반이기 때문)

 

---

2.  예시 (10진수 숫자 정렬)

초기 배열 : [170, 45, 75, 90, 802, 24, 2, 66]

1. 1의 자리 기준 정렬 → [170, 90, 802, 2, 24, 45, 75, 66]
2. 10의 자리 기준 정렬 → [802, 2, 24, 45, 66, 170, 75, 90]
3. 100의 자리 기준 정렬 → [2, 24, 45, 66, 75, 90, 170, 802]

정렬 완료

 

---

3.  언어별 구현 예시 (10진수 양의 정수 기준)

a.  Python

def counting_sort(arr, digit):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    for num in arr:
        index = (num // digit) % 10
        count[index] += 1

    for i in range(1, 10):
        count[i] += count[i - 1]

    i = n - 1
    while i >= 0:
        index = (arr[i] // digit) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1
        i -= 1

    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_num = max(arr)
    digit = 1
    while max_num // digit > 0:
        counting_sort(arr, digit)
        digit *= 10

2.  C++

void countingSort(vector<int>& arr, int exp) {
    int n = arr.size();
    vector<int> output(n);
    int count[10] = {0};

    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = n - 1; i >= 0; i--) {
        int idx = (arr[i] / exp) % 10;
        output[--count[idx]] = arr[i];
    }

    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

void radixSort(vector<int>& arr) {
    int maxVal = *max_element(arr.begin(), arr.end());
    for (int exp = 1; maxVal / exp > 0; exp *= 10)
        countingSort(arr, exp);
}

c.  Java

void countingSort(int[] arr, int exp) {
    int[] output = new int[arr.length];
    int[] count = new int[10];

    for (int num : arr)
        count[(num / exp) % 10]++;

    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    for (int i = arr.length - 1; i >= 0; i--) {
        int idx = (arr[i] / exp) % 10;
        output[--count[idx]] = arr[i];
    }

    for (int i = 0; i < arr.length; i++)
        arr[i] = output[i];
}

void radixSort(int[] arr) {
    int max = Arrays.stream(arr).max().getAsInt();
    for (int exp = 1; max / exp > 0; exp *= 10)
        countingSort(arr, exp);
}

d.  JavaScript

function getMax(arr) {
  return Math.max(...arr);
}

function countingSort(arr, exp) {
  const output = new Array(arr.length).fill(0);
  const count = new Array(10).fill(0);

  for (let num of arr) {
    const digit = Math.floor(num / exp) % 10;
    count[digit]++;
  }

  for (let i = 1; i < 10; i++) {
    count[i] += count[i - 1];
  }

  for (let i = arr.length - 1; i >= 0; i--) {
    const digit = Math.floor(arr[i] / exp) % 10;
    output[--count[digit]] = arr[i];
  }

  for (let i = 0; i < arr.length; i++) {
    arr[i] = output[i];
  }
}

function radixSort(arr) {
  let max = getMax(arr);
  for (let exp = 1; Math.floor(max / exp) > 0; exp *= 10) {
    countingSort(arr, exp);
  }
}

 

---

4.  시간 복잡도 분석

케이스	시간 복잡도
최선	O(nk)
평균	O(nk)
최악	O(nk)
공간 복잡도	O(n + k)
정렬 안정성	안정 정렬

• n : 요소 수
• k : 자릿수 (예: 최대값 999면 k=3)
• 자릿수가 작을수록 성능이 좋습니다.
• 계수 정렬이 안정 정렬일 경우, 전체 정렬도 안정적입니다.

 

---

5.  마무리

• 기수 정렬은 자릿수를 기준으로 데이터를 분류하고 정렬하는 비비교 기반 정렬 알고리즘입니다.
• 정수나 고정 형식 문자열 등에서 빠른 성능을 발휘하며, 안정 정렬이 가능합니다.
• 일반적인 비교 기반 정렬과는 성격이 다르며, 특정 조건에서만 유효한 정렬 방식입니다.

함께 보면 좋은 자료

외부 사이트 :

• Wikipedia - Radix Sort

블로그 글 :

[정렬] 꼭 알아야 할 7가지 정렬 알고리즘 비교 정리

 

---

반응형