[알고리즘] 기수 정렬(Radix Sort)이란 ?

📁기수 정렬

낮은 자리수부터 비교하여 정렬해간다는 것을 기본 개념으로 하는 알고리즘으로 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다는 단점이 있다.

1️⃣ 기수 정렬의 과정

• LSD(Least Significant Digit) 방식의 정렬

1. 데이터 중 가장 큰 자리수를 구한다.
   1-1. 배열의 요소 중 가장 큰 값을 찾는다.
   1-2. 가장 큰 값을 i(i = 10⁰, 10¹, ...)로 나눈 값이 0보다 크지 않으면 arr의 요소가 모두 i보다 작다는 의미를 가지므로 가장 큰 자리수를 구할 수 있다.
2. 가장 작은 자릿수부터 가장 큰 자릿수까지 해당 자릿수만을 보고 Counting Sort를 진행한다.

import java.util.*;

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = new int[] {38, 27, 43, 3, 9, 82, 10, 22};

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

    // 기수 정렬
    static void radixSort(int[] arr) {
        int max = 0;
        for(int i = 0; i < arr.length; i++) {
            max = Math.max(arr[i], max); // 배열의 요소 중 가장 큰 값을 찾는 과정
        }

        // 가장 큰 값 / i가 0보다 크지 않다면 arr의 요소가 모두 i보다 작다는 의미
        for(int i = 1; max / i > 0; i*=10) {
            countSort(arr, i);
        }
    }

    // 개수 정렬 시작
    static void countSort(int[] arr, int digit) {
        Map<Integer, Queue<Integer>> map = new HashMap<>(); // 큐를 보관할 Map 선언

        for(int i = 0; i < arr.length; i++) {
            int value = (arr[i] / digit) % 10; // (arr의 요소 / digit) % 10 -> digit 자릿수의 숫자만 추출

            Queue<Integer> queue = map.getOrDefault(value, new LinkedList<>()); // 해당 키의 큐가 존재하면 map에서 가져오고 그렇지 않다면 생성
            queue.offer(arr[i]); // 큐에 arr의 요소를 정렬된 순서대로 넣는다.

            map.put(value, queue);
        }

        List<Integer> keySet = new ArrayList<>(map.keySet()); // map의 키를 오름차순 정렬
        Collections.sort(keySet);

        int index = 0;
        // 키가 0인 큐부터 차례대로 존재하는 큐의 요소를 모두 arr에 기존 자리의 값을 초기화하며 정렬
        for(int i = 0; i < keySet.size(); i++) {
            Queue<Integer> queue = map.get(keySet.get(i));

            while (!queue.isEmpty()) {
                arr[index++] = queue.poll();
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

2️⃣ 기수 정렬 정리

1. 기수 정렬은 O(dn)의 시간 복잡도를 가지고 있어 매우 빠른 정렬 알고리즘이다. 이 때 d는 자릿수의 최댓값이다.

2. 비교 연산을 하지 않아 동일하 값의 원소가 입력에 따라 순서를 보장하는 안정 정렬(Stable Sort) 알고리즘이다.

3. 최선과 최악의 경우에도 항상 동일한 시간 복잡도를 가진다.

4. 데이터 전체 크기에 기수 테이블의 크기만한 추가적인 메모리가 필요하다.

5. 기수 정렬은 정렬 방법의 특수성 때문에, 부동소숫점 실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 사용 가능할 때에는 매우 효율적인 알고리즘이다.