스윙스만큼(?) 빠른 기수 정렬(Radix Sort)에 대해 친절하게 알려드림

 

* 중요 : Big-O 표기법에서 상수 인자는 무시한다. 계수 정렬과 기수 정렬은O(N)의 시간 복잡도를 가지고 있으나 상수 인자 크기에 따라(자리수에 따라) 생각만큼 빠르지 않을 수 있으며, 리얼 월드에서는 Cache Hit까지 고려하면 계수 정렬을 사용할 수 있는 상황에서도 O(nlogn)의 시간 복잡도를 가진 Quick sort보다 빠르지 않을 수도 있다.

다만 기수 정렬은 Bucket sort와도 관련이 있으므로 구현에 대해서는 한 번 배워놓는 것을 추천한다.

 

간만에 새로운 정렬 알고리즘 하나 배워왔다.

마지막에 올렸던 Counting sort의 형뻘 정도 되는 Radix sort, 계수 정렬이다.

 

Counting sort가 뭔지 궁금하다면 아래 글을 읽어보자.

사실 굉장히 쉬워서 굳이 읽지 않아도 된다.

짧게 설명하자면 정렬하려는 배열의 최대값 크기만큼의 배열을 만들고, 해당 배열의 각 인덱스에 기존 배열 값을 대응하여 죄다 밀어넣고, 다시 순서대로 꺼내면 그게 계수 정렬이다.

 

https://7357.tistory.com/152?category=1065986 

계수 정렬(Counting sort)에 대해 알아보자

 

언뜻 봐도 상당히 비효율적인 방법이란 것을 알 수 있다.

1, 4, 10000000이라는 값을 가진 이상한 배열이 있을 때, 계수 정렬 방식으로는 10000000크기의 배열을 만들어야하니 말이다.

 

그러나 계수정렬의 시간복잡도인 O(N)은 그런 단점이 있다는 이유만으로 포기하긴 침 나오는 속도다.

이번에는 구현은 다소 복잡하지만, 저 침나오는 시간 복잡도를 유지하면서도 보다 효율적인 방법인 기수 정렬을 알아보자.

 

 

 

기수 정렬은 계수 정렬과 마찬가지로 비교를 하지 않는 정렬이다.

그리고 계수 정렬과 마찬가지로 음수는 음수끼리만 정렬 가능하며, 정수는 정수끼리만 정렬 가능하고, 최대값이 정해진 경우에만 사용 가능하며, 내부 정렬이 아니라 별도의 메모리 공간을 필요로하는 정렬이라는 단점이 있다.

 

그럼에도 불구하고 시간 복잡도가 O(N)이기 때문에 해당 알고리즘을 적용 가능한 상황에서는 굉장히 좋다다.

위에서 계수 정렬보다 기수 정렬이 효율적이라고 언급했는데, 그 위 gif를 보다시피 기수정렬은 최대값만큼의 임시 배열을 요구하지 않는다.

 

기수 정렬에 필요한 것은 range(정렬하려는 범위, 숫자라면 일반적으로 10이겠지만 문자열 정렬 시에도 사용 가능하다.)의 배열과 원본 배열과 같은 크기의 배열 뿐이다.

아까 언급했던 1, 4, 10000000의 이상한 배열에서 계수 정렬은 new int[10000000]의 배열을 요구하지만, 기수 정렬은 고작 3칸짜리 배열과 10칸짜리 배열 두개면 된다는 말이다.

 

기수 정렬은 내부적으로 계수 정렬을 활용하여 각 자리수끼리 비교하는 것을 최대 크기 숫자의 자리수만큼 반복하는 방식을 택한다.

 

ex ( 9, 47, 244를 비교한다면 처음에는 9가 가장 마지막 인덱스를 차지하겠지만 2번째, 3번째 비교에서는 해당 자리수가 0이므로 앞으로 밀려난다 )

 

다만 제일 위의 "중요"에서 언급했던 부분인데, 자리수만큼 연산 횟수가 늘어난다.

기수 정렬의 시간 복잡도는 뭐다? O(N)이다.

그런데 여기에는 함정이 있다. big-O 표기법에서 상수는 생략한다. 즉 O(3N)이든 O(100N)이든 모두 O(N)으로 취급한다는 말이다.

따라서 자리수가 늘어날수록 연산 속도가 느려지며, 이 부분 때문에 기수 정렬이 "항상" O(nlogn)의 정렬보다 빠르다고 할 수는 없다.

 

장단점을 모두 설명했으니 바로 구현을 보자.

소스코드는 baeldung을 참고하여 설명을 덧붙였다.

 

https://www.baeldung.com/java-radix-sort

Radix Sort in Java | Baeldung

 

 

public static void radix_sort(int[] arr, int placeValue) {
        int[] bucket = new int[10];
        int[] temp = new int[arr.length];
 
        int range = 10;
        // 지금 당장은 무의미한 변수 같겠지만 기수 정렬은 문자열 정렬 등에도 사용할 수 있음을 생각하자.
 
        for (int i=0; i<arr.length; i++) {
            bucket[(arr[i]/placeValue)%10]++;
        }
 
        for (int i=1; i<range; i++) {
            bucket[i] += bucket[i-1];
            // 이해 안되면 아래 설명을 읽자.
        }
 
        for (int i=arr.length-1; i>=0; i--) {
            int digit = (arr[i]/placeValue)%10;
            temp[bucket[digit]-1] = arr[i];
            bucket[digit]--;
            // 이해 안되면 아래 설명을 읽자.
        }
 
        for (int i=0; i<arr.length; i++) {
            arr[i] = temp[i];
        }
    }

 

사람마다 다르겠지만 난 보자마자 이해가 되지는 않았다.

 

우선, 해당 함수만 별도로 꺼내왔기 때문에 설명이 필요한 상황이다.

이 함수는 배열 최대값의 자리수만큼 반복하며 호출된다.

따라서 {100, 32, 9, 73}의 배열이라면 해당 함수가 3번 호출되는 것이며, 1의 자리 수부터 한 자리씩 올라가며 정렬하고 있는 것이다.

(즉, placeValue라는 변수가 1부터 10씩 곱해지며 반복된다)

 

지금부터 나의 발그림으로 함수 내에서 일어나고 있는 일들을 친절하게 설명을 해볼테니, 이해가 안되거나 도저히 글씨 때문에 보기 힘들면 다른 곳을 찾아가보자.

 

 

 

        for (int i=0; i<arr.length; i++) {
            bucket[(arr[i]/placeValue)%10]++;
        }

{9, 43, 22, 73}의 값을 가진 배열이 해당 함수에 들어왔다고 가정하자.

첫 번째 호출 시에는 1의 자리 수를 비교하기 때문에 제일 위의 반복문에서 Bucket의 2번째 인덱스는 1, 3번째 인덱스는 2, 9번째 인덱스는 1이 될 것이다.

 

 

잘못 썼다.. 누적합이기 때문에 45678도 모두 3이여야 하는데, 중요한 것은 아니니 넘어가자.

 

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

 

여기서 혼란이 올 수 있다. 침착하자.

뜬금없이 bucket에 누적합을 구하고 있는데, 이것은 우리가 정렬한 값이 몇 번째 인덱스로 가야하는지를 의미한다.

1,3,4를 보고 인덱스를 어떻게 아냐고 생각할 수 있다.

 

아래 내용을 보면 이해할 수 있으니 빠르게 넘어가자.

 

 

        for (int i=arr.length-1; i>=0; i--) {
            int digit = (arr[i]/placeValue)%10;
            temp[bucket[digit]-1] = arr[i];
            bucket[digit]--;
        }

 

 

위 그림과 연계하며 이해해보자.

우선 digit을 다시 구한다. digit은 arr[i]의 n번째 수다.

그리고 temp 배열은 arr[i]에 대입해주기 위해 만들어놓은 임시 배열이다.

 

bucket[digit]은 우리가 누적합을 구해놨기 때문에 bucket[digit]까지 총 몇 개의 인자가 있는지 알 수 있다.

즉 temp의 몇 번째 자리에 해당 digit을 가진 arr[i]가 들어가야하는지 정해놨다는 것이다.

 

digit이 9인 경우 bucket[9]는 4이므로 temp의 4번째 자리에 해당 자리수가 9인 arr[i]가 들어간다.

엥?? 그런데 해당 자리수가 여러개면 어떡해요??

 

bucket[digit]--;로 1회 반복 시마다 bucket[digit]의 값이 1씩 줄어들고 있다.

만약 9가 두 번 나오면 다음 9를 가진 숫자는 temp[3]으로 들어가게 될 것이다.

 

이제 해당 함수 내부의 코드에 대해서는 충분히 이해가 됐으리라 생각한다.

그러면 마지막으로 제일 헷갈릴만한 부분이다.

 

왜 i가 arr.length-1부터 i>=0으로 1씩 줄어들며 반복하는가?

왜 0부터 더해서 반복하면 배열이 엉망진창이 되는가?

 

만약 {9, 43, 41, 7}이라는 값을 가진 배열이 해당 함수에 들어간다면, 처음 정렬된 상태는 {41, 43, 7, 9}가 될 것이다.

여기까지는 아무런 문제가 없다.

 

그런데 만약 해당 반복문을 0부터 증가하게 둔다면, 41이 43보다 뒤에 위치하게 된다.

그러나 arr.length(즉, 4)부터 감산하며 반복한다면 43이 41보다 뒤에 위치하여 정상적인 배열이 완성된다.

 

왜냐면 기수 정렬은 특정 자리수만 가지고 비교하는 것이지, 이전에 1의 자리 기준으로 어떻게 정렬됐었는지 그런건 알 바 아니고 해당 배열을 체크해보니 7과 9는 1번, 0번 인덱스에 들어가도록 되어있고 4는 3번,4번 인덱스에 들어가도록 되어있을 것이다.

 

그러면 당연히 먼저 만난 41이 제일 끝자리인 4번 인덱스에 들어가고, 그 다음으로 만난 43이 3번 인덱스에 들어간다.

이런 현상을 막기 위해서는 해당 자리수가 같을 경우 기존 정렬된 상태를 유지하며 정렬될 수 있도록 뒤의 인덱스부터 순차적으로 정렬해야 한다.

 

후.. 내가 본 기수 정렬 글중에 진짜 제일 친절하다.

혹시 자리수를 구하는 방법이나 최대값 구하는 방법까지 알려줄 필요는 없다고 믿겠다.

기껏 배워봤으니 썩혀두지 말고 바로 백준으로 달려가서 수 정렬하기 문제를 풀어보자.

 

 

 

 

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

 

 
import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] temp = new int[N];
 
        for (int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
 
        int maxValue = getMaxValueIn(arr);
        int digits = getDigits(maxValue);
        int placeValue = 1;
 
        while (digits-- > 0) {
            radix_sort(arr, placeValue);
            placeValue*=10;
        }
 
        StringBuilder sb = new StringBuilder();
        for (int i=0; i<arr.length; i++) {
            sb.append(arr[i]).append("\n");
        }
 
        System.out.println(sb);
    }
 
    private static int getDigits(int maxValue) {
        int count = 0;
        while (maxValue>0) {
            maxValue/=10;
            count++;
        }
        return count;
    }
 
    private static int getMaxValueIn(int[] arr) {
        int max = 0;
        for (int i=0; i<arr.length; i++) {
            max = Math.max(arr[i], max);
        }
        return max;
    }
 
    public static void radix_sort(int[] arr, int placeValue) {
        int[] bucket = new int[10];
        int[] temp = new int[arr.length];
 
        int range = 10;
 
        for (int i=0; i<arr.length; i++) {
            bucket[(arr[i]/placeValue)%10]++;
        }
 
        for (int i=1; i<range; i++) {
            bucket[i] += bucket[i-1];
        }
 
        for (int i=arr.length-1; i>=0; i--) {
            int digit = (arr[i]/placeValue)%10;
            temp[bucket[digit]-1] = arr[i];
            bucket[digit]--;
        }
 
        for (int i=0; i<arr.length; i++) {
            arr[i] = temp[i];
        }
    }
}