자료구조 - 정렬 6 (Radix)

 

전체 정렬 개요의 설명은 여기를 참조
Bubble / Selection / Insertion 정렬의 설명은 여기를 참조
Shell 정렬의 설명은 여기를 참조
Merge 정렬의 설명은 여기를 참조
Quick 정렬의 설명은 여기를 참조
Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 여기를 참조
Counting 정렬의 설명은 여기를 참조
Bucket 정렬의 설명은 여기를 참조
Topological 정렬의 설명은 여기를 참조

 

 

Radix Sort (기수 정렬)

 

이전의 버블 / 선택 / 삽입 / 병합 / 퀵 정렬 등은 모두 값을 비교함으로써 정렬을 수행하게 되고 이는 아무리 좋은 성능을 낼지라도 평균적으로 O(nlogn)보다 더 빠르게 수행할 수는 없다.

그런데, 이전의 Counting Sort(계수 정렬)과 같이 데이터의 특성을 잘 이용하면 거의 선형 시간에 가깝게 정렬을 수행할 수 있었다.

하지만, Counting Sort(계수 정렬)은 모든 상황에 사용할 수는 없다. 만약 데이터의 크기와 데이터 값이 너무 차이가 심하다면 오히려 더욱 성능이 안좋아진다.

예를 들어 길이는 n인데 데이터의 크기는 0부터 n^2 까지 있다면 결국 O(n^2)의 성능으로 동작하게 되기 때문이다.

그럼, 그런 데이터 배열이 있을 때, 어떻게 선형 시간 복잡도 수준으로 해결할 수 있을까? 바로 기수 정렬이 그 답이 될 수 있다.

 

기수 정렬을 이해해보기 위한 그림은 다음과 같다.

 

 

기수 정렬의 개념은 각 데이터 값의 자리수와 자리수의 값을 이용해 반복적으로 Counting Sort를 수행하여 전체 배열을 정렬하는 방식이다.

1의 자리가 아무리 큰 숫자라도 10의 자리가 더 큰 숫자가 더 큰 숫자가 된다. 그래서 전체 자리수에는 가장 덜 중요한 자리수와 중요한 자리수가 나뉘어진다.

LSD : Least Significant Digit으로 숫자로는 1의 자리수를 의미한다.
MSD : Most Significant Digit으로 숫자로는 자리수가 최대 d라면 d의 자리수를 의미한다.(예, 5000이면 천의 자리수)

어느 자리수를 먼저 기준으로 정렬하느냐에 따라 LSD 방식, MSD 방식으로 나뉜다.

LSD 방식은 구현에 있어서 더욱 편의적이어서 LSD 방식으로 실제로는 많이 구현한다. 그러나 MSD 방식은 꼭 모든 자리수에 대해 다 검증하지 않아도 된다는 장점이 있다.

 

기수 정렬의 특징은 다음과 같다.

 

특성	설명
Not In-place 알고리즘	배열을 나누는 과정에서 나누어진 배열을 별도로 저장할 공간이 필요하다.
Stable 알고리즘	같은 값의 데이터의 기존 순서 유지를 보장할 수 있다.

 

기수 정렬의 시간  / 공간 복잡도는 아래와 같다.

알고리즘	시간복잡도(최상)	시간복잡도(평균)	시간복잡도(최악)	공간복잡도
기수 정렬	O(nw)	O(nw)	O(nw)	O(n)

 

시간복잡도 부분에서 w는 기수의 크기이다. 즉, 몇의 자리수까지 있느냐를 의미하여 거의 상수이기 때문에 실질적으로 O(n) 수준의 성능을 보여준다.

 

Counting Sort(계수 정렬)을 이해했다면 기수 정렬은 이해하기 쉽다. 코드로 이해해보자.

 

 

코드로 구현

 

아래는 LSD 방식으로 작은 자리수부터 먼저 정렬하는 방식의 코드이다.

package com.test;

public class LSDRadisSort {
    public static void main(String[] args){

        // 전체 크기는 30으로 제한
        int[] arr = new int[30];
        for(int i=0; i < arr.length; i++){
            // Math.random을 통해 값의 범위는 0 ~ 99999 까지로 제한
            arr[i] = (int)(Math.random()*100000);
        }

        radixSort(arr);
        // 출력
        for(int i=0; i < arr.length; i++){
            System.out.print(arr[i] + ", ");
        }
    }

    public static void radixSort(int[] arr){
        // 최대값을 가져온다.
        int max = getMax(arr);

        // 모든 digit에 대해 counting 정렬을 수행한다.
        // 여기선 1의 자리부터 수행하므로 LSD 방식임
        for(int exp = 1; max / exp > 0; exp *= 10){
            countingSort(arr, exp);
        }
    }

    private static int getMax(int[] arr){
        // 전체 배열 중 최대값을 구한다.
        int max = arr[0];
        for(int i=1; i < arr.length; i++){
            if(arr[i] > max){
                max = arr[i];
            }
        }
        return max;
    }

    public static void countingSort(int[] arr, int exp){
        // 각 자리수의 수가 얼마나 나왔는지 체크하는 배열
        // 숫자는 0 ~ 9 까지니까 10개 size로 만들면 된다.
        int[] count = new int[10];

        // result 배열도 생성 ( 정렬이 완료된 배열이므로 기존 배열 크기와 동일하게 설정)
        int result[] = new int[arr.length];

        // 각 배열의 값이 몇 번 나왔는지 넣어주자.
        // exp로 나누고 10으로 나눈 나머지를 구하면 현재 자리수의 값을 구할 수 있다.
        for(int i=0; i < arr.length; i++){
            count[(arr[i] /exp) % 10]++;
        }

        // count 배열의 누적합을 구함(Modify)
        for(int i=1; i < count.length; i++){
            count[i] += count[i-1];
        }

        // count 배열은 사실상 어디에 위치시킬지 값을 저장한 Modified 배열이므로 그 값을 통해서 result 배열에 원래 값을 저장
        for(int i = arr.length-1; i >= 0; i--){
            result[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

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

 

MSD 방식은 구현에 있어 LSD 대비 난이도가 높아 대부분 LSD 방식으로 구현한다. (추후 별도 추가 예정..)

 

읽어주셔서 감사합니다. 오류가 있으면 댓글로 남겨주시면 반영하겠습니다.

감사합니다.