기수 정렬 (Radix Sort) 총 정리 - 개념, 원리, 동작 예시, 시간 복잡도, C언어, Java, Python 예시코드, 주의점, 장단점

기수 정렬(Radix Sort)

 

 

 

1. 기수 정렬이란?

기수 정렬은 정수를 자리수별로 비교하여 정렬하는 정렬 알고리즘입니다. 가장 낮은 자리수부터 높은 자리수까지 순차적으로 정렬하는 방식(LSD: Least Significant Digit) 또는 높은 자리수부터 낮은 자리수로 정렬하는 방식(MSD: Most Significant Digit)을 사용합니다.

계수 정렬을 서브 루틴으로 활용하며, 데이터의 크기와 범위에 따라 매우 효율적입니다.

 

기수 정렬을 이해하기 위해서는 계수정렬(Counting Sort)에 대한 이해가 선행되어야 합니다.해당 개념은 아래 포스팅에 자세히 정리했습니다.

2025.01.02 - [알고리즘] - 계수 정렬 (Counting Sort) 총 정리 - 개념, 원리, 동작 예시, 시간 복잡도, C언어, Java, Python 예시코드, 주의점, 장단점

계수 정렬 (Counting Sort) 총 정리 - 개념, 원리, 동작 예시, 시간 복잡도, C언어, Java, Python 예시코드,

 

---

 

 

2. 원리

1. 정렬할 데이터의 최대 자릿수를 결정합니다.
2. 가장 낮은 자리수부터 시작하여 계수 정렬을 반복합니다.
3. 각 단계에서 해당 자리수를 기준으로 정렬된 배열을 생성합니다.
4. 모든 자리수를 처리하면 최종 정렬된 배열이 완성됩니다.

---

 

 

3. 동작 예시 (구체적인 설명)

정렬할 배열: [170, 45, 75, 90, 802, 24, 2, 66]

1. 최대 자릿수 결정:
   • 최대값 802는 3자리이므로, 3회 반복이 필요합니다.
2. 1의 자리수 기준 정렬:
   • 자리수 추출: [0, 5, 5, 0, 2, 4, 2, 6]
   • 계수 정렬 수행: [170, 90, 802, 2, 24, 45, 75, 66]
3. 10의 자리수 기준 정렬:
   • 자리수 추출: [7, 9, 0, 0, 2, 4, 7, 6]
   • 계수 정렬 수행: [802, 2, 24, 45, 66, 170, 75, 90]
4. 100의 자리수 기준 정렬:
   • 자리수 추출: [8, 0, 0, 0, 0, 1, 0, 0]
   • 계수 정렬 수행: [2, 24, 45, 66, 75, 90, 170, 802]
5. 최종 정렬 완료:
   • 결과: [2, 24, 45, 66, 75, 90, 170, 802]

반응형

---

 

 

4. 시간 복잡도

• 시간 복잡도: O(d * (n + k))
  • d: 자릿수의 개수
  • n: 데이터의 개수
  • k: 자릿수 값의 범위 (일반적으로 10)
• 공간 복잡도: O(n + k)

---

 

 

5. 코드 예제

C 코드

#include <stdio.h>
#include <string.h>

void countingSort(int arr[], int n, int exp) {
    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--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

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

void radixSort(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max)
            max = arr[i];

    for (int exp = 1; max / exp > 0; exp *= 10)
        countingSort(arr, n, exp);
}

int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);

    radixSort(arr, n);

    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

 

Java 코드

import java.util.Arrays;

public class RadixSort {

    public static 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--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

        System.arraycopy(output, 0, arr, 0, arr.length);
    }

    public static void radixSort(int[] arr) {
        int max = Arrays.stream(arr).max().orElse(0);

        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};

        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

 

Python 코드

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

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

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

    for i in range(n - 1, -1, -1):
        index = (arr[i] // exp) % 10
        output[count[index] - 1] = arr[i]
        count[index] -= 1

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

def radix_sort(arr):
    max_val = max(arr)
    exp = 1

    while max_val // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

arr = [170, 45, 75, 90, 802, 24, 2, 66]
radix_sort(arr)
print(arr)

---

 

 

6. 주의점

1. 기수 정렬은 정수 또는 자릿수로 나눌 수 있는 데이터에 적합합니다.
2. 계수 정렬을 서브 루틴으로 사용하므로 추가적인 메모리 소비가 발생합니다.

---

 

 

7. 장단점

장점

• 매우 빠른 성능 (O(d * (n + k))).
• 데이터의 크기와 범위가 적당하다면 효율적.

단점

• 범용성이 떨어짐 (정수와 자릿수 기반 데이터에만 사용 가능).
• 계수 정렬의 한계를 공유.

 

함께 보면 좋은 글

코딩 테스트에 나오는 거의 모든 정렬 알고리즘들에 대해 비교했습니다. 언제 어떤 정렬 알고리즘을 쓰면 좋은지에 대해서도 작성했습니다. 아래 링크에 자세히 작성했습니다.

 

2025.01.03 - [알고리즘] - 정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주요 특징, 상황에 따른 선택 기준

정렬 알고리즘 총 정리 및 비교 - 각 알고리즘 별 장단점, 시간 복잡도, 공간 복잡도, 안정성, 주