기수정렬(Ridix Sort)

기수정렬(Ridix Sort)

개념

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

로직

1. 데이터 중 가장 큰 자리수를 구합니다.
2. 가장 작은 자리수부터 가장 큰 자리수까지 해당 자리수만을 보고 Conting Sort를 진행합니다.

위 GIF 이미지는 Queue를 사용한 방식을 더 잘 표현하는 것 같다.

코드

RadixSort.java

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class RadixSort {

    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        radixSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    private static void radixSort(int[] arr) {
        // 최대값 구하기
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (max < arr[i])
                max = arr[i];
        }

        // Counting Sort를 사용하여 해당 자리 정렬하기.
        for (int digit = 1; digit <= max; digit *= 10) {
            countingSort(arr, digit);
        }
    }

    private static void countingSort(int[] arr, int digit) {
        int[] temp = new int[N]; // 임시로 사용할 공간
        int[] counting = new int[10]; // 카운팅 배열

        for (int i = 0; i < N; i++) {
            int num = (arr[i] / digit) % 10; // 해당 자리수의 숫자 추출
            counting[num]++;
        }

        // 누적합 배열로 만들기
        for (int i = 1; i < counting.length; i++) {
            counting[i] += counting[i - 1];
        }

        // 뒤에서 부터 시작 >> 값이 큰것이 뒤로 가야하기 때문
        for (int i = 0; i < N; i++) {
            int num = (arr[i] / digit) % 10;
            int index = counting[num];

            temp[index - 1] = arr[i];
            counting[num]--;
        }

        // 복사
        for (int i = 0; i < N; i++) {
            arr[i] = temp[i];
        }
    }

}

console

정렬 전: [40, 58, 27, 29, 95, 33, 76, 93, 39, 36]
정렬 후: [29, 27, 39, 36, 33, 40, 58, 76, 95, 93]

시간복잡도

배열에서 가장 큰 자리수의 값만큼 Counting Sort를 수행한다. 만약 배열의 최대 원소의 값이 1350이라면 총 4번을 수행하게 됩니다.

한번의 Counting Sort는 $O(n+k)$의 시간복잡도를 같으며 $k=10$으로 $O(n)$으로 표현이 가능합니다.

따라서 정렬할 숫자의 자릿수를 $d$라고 하면 시간 복잡도는 $O(dn)$으로 표현 할 수 있습니다.

기수 정렬은 비교 연산을 하지 않으며, 무엇보다도 전체 시간 복잡도 역시 $O(dn)$이어서, 정수와 같은 자료의 정렬 속도가 매우 빠릅니다.

데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다. 기수 정렬은 정렬 방법의 특수성 때문에, 부동소수점실수처럼 특수한 비교 연산이 필요한 데이터에는 적용할 수 없지만, 사용 가능할 때에는 매우 좋은 알고리즘이다.

장점

1. 자리수를 비교해 정렬하기때문에 문자열도 정렬이 가능하다.
2. $O(dn)$의 빠른시간으로 정렬이 가능
3. 안정 정렬 이다.

단점

1. 자릿수가 없는 것은 정렬이 불가능 하다.
2. 추가적인 메모리 공간이 필요하다.