기수 정렬 (Radix Sort)

기수 정렬 (Radix Sort) ?

• 기수 정렬은 각 자리 위치를 하나씩 증가시키면서 숫자들을 정렬하는 방법이다.
• 안정 정렬에 속하며, 카운팅 정렬과 마찬가지로 값의 비교연산 없이 정렬한다.
• 기수 정렬의 단점은 다음과 같다.
  • 제자리 정렬이 아니기 때문에 추가적인 메모리가 필요하다.
  • 동일한 길이를 가진 숫자나 문자열이여야 한다.
• 정렬하는 숫자 자릿수 \(k\) 에 따라 \(O(kn)\) 의 시간 복잡도를 가진다.
• 기수 정렬 과정은 다음과 같다.
  • 1의 자리 숫자를 비교해서 오름차순 또는 내림차순으로 정렬한 뒤, 큐 버킷에 삽입한 뒤 순서대로 뽑아 정렬한다.
  • 그 다음, 10의 자리 숫자를 비교해서 동일하게 수행한다.
  • 가장 큰 숫자의 자릿 수만큼 반복해서 수행한다.

 

Code

public static void radixSort(int[] arr, int maxSize) {
    int jarisu = 1, size = 0;
    int len = arr.length;
    int[] output = new int[len];

    while (size < maxSize) {
        int[] bucket = new int[10];

        for (int i = 0; i < len; ++i) {
            ++bucket[arr[i] / jarisu % 10];
        }

        for (int i = 1; i < 10; ++i) {
            bucket[i] += bucket[i - 1];
        }

        for (int i = len - 1; i >= 0; --i) {
            int idx = arr[i] / jarisu % 10;

            output[bucket[idx] - 1] = arr[i];
            --bucket[idx];
        }

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

        jarisu *= 10;
        ++size;
    }
}

 

 

결과

기수 정렬 1 단계:
[82, 43, 3, 15, 35, 27, 7, 38, 18, 9]
기수 정렬 2 단계:
[3, 7, 9, 15, 18, 27, 35, 38, 43, 82]

 

Reference

• https://lktprogrammer.tistory.com/48
• https://namu.wiki/w/정렬%20알고리즘#s-2.2.2