[알고리즘] 정렬 - 기수 정렬

1. 개념

일의 자리만 보고 정렬을 한다. 그 이후에 십의 자리만 보고 정렬을 한다. 즉 기수만 보고 정렬을 진행하는 것이다. 여기서 기수란 각 진수에서 표현할 수 있는 수를 말한다. 예를 들어 10진수면 기수는 0~9이다.

 

보통 이런 기수 정렬은 기수를 담을 큐를 만들어 놓고, 수를 기수에 맞는 큐에 넣었다 빼며 정렬을 진행한다.

예를 들어 10 32 11 25 이런 수가 있을 때, 0을 담는 큐를 만들고, 1을 담는 큐를 만들고... 9를 담는 큐를 만든다. 그리고 10의 일의자리는 0이니 0을 담는 큐에 10을 넣는다. 32의 일의자리는 2이니 2를 담는 큐에 32를 넣는다. 11의 일의자리는 1이니 1을 담는 큐에 11을 넣는다. 25의 일의자리는 5이니 5를 담는 큐에 25를 넣는다. 그리고 나서 0부터 시작해서 각 큐에 있는 수를 뺀다. 그러면 이 경우에는 10 11 32 25가 된다. 그리고 나서는 십의자리를 보고 큐에 넣었다 뺀다. 이를 끝내고 나면 결과는 10 11 25 32가 되고 정렬이 끝난다.

 

2. 특징

• 비교 연산이 없다
• 안정 정렬이다
• 제자리 정렬이 아니다. 정렬 과정에서 각 자릿수대로 수를 담을 공간이 추가로 필요하다.

 

3. 시간복잡도

원소의 개수가 n이라고 했을 때 n개의 데이터를 가장 긴 자릿수를 가진 수의 자릿수만큼 반복해서 정렬을 진행한다.

가장 긴 자릿수가 k라고 하면 결국 시간복잡도는 O(kn)이다.

 

4. 코드

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static final int bucketSize = 10;
    static final int positionLen = 2;
    public static void main(String[] args) throws IOException {
        int[] nums = {10, 44, 23, 45, 19};
        radixSort(nums.length, nums);
        for(int n : nums){
            System.out.println(n);
        }

    }

    public static void radixSort(int n, int[] nums){
        Queue<Integer>[] bucket = new LinkedList[bucketSize];
        for(int i = 0; i<bucketSize; i++){
            bucket[i] = new LinkedList<>();
        }
        int factor = 1;

        for(int d = 0; d < positionLen; d++){
            for(int i = 0; i<n; i++){
                bucket[(nums[i]/factor)%10].add(nums[i]);
            }
            for(int i = 0, j = 0; i<bucketSize; i++){
                while(!bucket[i].isEmpty()){
                    nums[j++] = bucket[i].poll();
                }
            }
            factor *= 10;
        }
    }
}

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    static final int bucketSize = 10;
    static final int positionLen = 5;
    public static void main(String[] args) throws IOException {
        int[] nums = {10, 44, 23, 45, 19};
        radixSort(nums);
        for(int n : nums){
            System.out.println(n);
        }

    }

    public static void radixSort(int[] nums){
        int[] output = new int[nums.length];
        int jarisu = 1;
        int count = 0;
        while(count != positionLen){
            int[] bucket = new int[10];
            // 각 숫자의 자릿수를 살펴서 알맞는 버켓의 값을 1 올리기
            for(int i = 0; i<nums.length; i++){
                bucket[(nums[i]/jarisu) % 10]++;
            }
            // 위에서 구한 버켓을 보고 구간 합으로 바꾸기
            for(int i = 1; i<10; i++){
                bucket[i] += bucket[i-1];
            }
            // 원래 배열 맨 뒤부터 살피면서 정렬
            for(int i = nums.length-1; i>=0; i--){
                output[bucket[(nums[i]/jarisu % 10)] - 1] = nums[i];
                bucket[(nums[i] / jarisu) % 10]--;
            }
            // 정렬 결과 원래 배열로 복사
            for(int i = 0; i<nums.length; i++){
                nums[i] = output[i];
            }
            jarisu = jarisu * 10;
            count++;
        }
    }
}

구간합의 의미

• 결국 이 구간합은 배열 원소를 해당 기수를 보고 정렬한 것의 index를 나타내게 된다(사실 index+1, 그래서 아래 for문에서 1을 빼줌)(겹치는 거 없다고 가정)
• 만약 일의 자리수를 보고 정렬을 먼저 하고 있다고 할 때, 1의 버켓이 1, 3의 버켓이 2, 7의 버켓이 3, 8의 버켓이 4라고 하자.
• 그러면 일의 자리수를 보고 정렬한 결과는 일의 자리가 1인 게 첫번째, 일의 자리가 2인 게 두번째,... , 이렇게 되는 것이다.
• 그래서 원래 배열의 일의 자리수를 다시 봐서 해당 일의 자리수의 버켓에 있는 인덱스가 그 배열 원소의 index가 되는 것이다(하지만 배열 인덱스는 0부터 시작이니 우리는 1을 빼준다)
• 한 번 예시를 돌려보면 이해가 된다

 

5. 관련 문제

백준 10989