[Data Structure] 기수 정렬 - Radix Sort

기수 정렬 (Radix Sort)

Stable Sort

• 비교하지 않는 정렬 알고리즘
• 기수(radix) = 숫자의 자리수 → ex) 42 = 4와 2의 2개의 자리수 보유
• 십진수에서 각 자리수는 0~9까지의 값만 가지기 때문에 10개의 버킷을 생성해서 (0, 1, 2,....9) 숫자의 기수에 맞게 버킷에 집어넣는다
• 낮은 숫자의 버킷부터 차례대로 해당 버킷의 값을 꺼내면서 정렬
• 큐(Queue)로 구현하면 편리하게 구현 가능

 

 

 

숫자가 10 이상일 경우

1. 자릿수가 2개가 존재하기 때문에, 먼저 1의 자리수를 기준으로 버킷에 집어넣는다

2. 1의 자리수를 기준으로 insert된 버킷에서 각 숫자를 꺼낸다음에 십의 자리수를 기준으로 버킷에 집어넣고, 버킷에서 꺼내면 정렬이 완료된다

 

 

정렬할 배열 A, 10개의 Bucket 필요 (0 ~ 9)

 

 

시간복잡도

- O(nk) → k = 자릿수 개수

 

장점

- O(n)의 매우 빠른 속도로 정렬 가능

 

단점

- 정렬할 수 있는 레코드의 타입이 동일한 길이를 가지는 숫자/문자열로 한정되어 있다

- 추가적인 메모리가 필요하다

 

과정

1. 10개의 Bucket 준비 (Bucket : 0 ~ 9)
2. 배열의 요소 중 최대 자릿수를 가지는 요소의 자릿수 return
3. 배열의 각 요소들의 1의 자릿수를 기준으로 Queue에 각각 삽입
4. Queue 0 ~ 9까지 차례대로 요소들을 꺼내서 배열에 다시 저장
5. 배열의 각 요소들의 10의 자릿수를 기준으로 다시 Queue에 각각 삽입
6. Queue 0 ~ 9 까지 차례대로 요소들을 꺼내면 정렬 완료

 

 

Radix_Sort Code

static void radix_sort(int[] A, LinkedList[] bucket, int[] result){
        for(int i=0; i<10; i++)
            bucket[i] = new LinkedList<>(); // bucket 10개 생성

        int radix = 1;
        while(radix<get_max_radix(A))
            radix*=10; // 요소 중 최댓값의 자릿수 확인

        for(int i=1; i<radix; i*=10){
            for(int j=0; j<A.length; j++){
                int p = (A[j]/i)%10; // 각 숫자의 자릿수(작은 자릿수부터)
                bucket[(A[j]/i)%10].offer(A[j]);
            }
            int index = 0;
            for(int k=0; k<10; k++){
                while(bucket[k].size() != 0){
                    A[index] = (int) bucket[k].peekFirst();
                    bucket[k].pollFirst();
                    index++;
                }
            }

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

 

 

 

Full Code

package Sort;

import java.util.*;
public class Radix_Sort_2 {
    public static void main(String[] args) {
        int [] A = new int[30]; // 정렬할 배열 A
        int [] result = new int[30]; // A의 최종 정렬 배열 저장
        LinkedList [] bucket = new LinkedList[10]; // 0 ~ 9 저장하는 bucket 10개

        for(int i=0; i<A.length; i++)
            A[i] = (int)(Math.random()*201); // 0~200

        // 정렬 전 A 출력
        System.out.println("A[]");
        for(int i=0; i<A.length; i++){
            if(i%10==0) System.out.println();
            System.out.print(A[i] + "\t");
        }
        System.out.println("\n");

        radix_sort(A, bucket, result);
    }

    static int get_max_radix(int [] A){
        // 요소 중 자릿수 최대인 요소
        int max = A[0];
        for(int i=1; i<A.length; i++){
            if (A[i] > max)
                max = A[i];
        }
        return max;
    }

    static void radix_sort(int[] A, LinkedList[] bucket, int[] result){
        for(int i=0; i<10; i++)
            bucket[i] = new LinkedList<>(); // bucket 10개 생성

        int radix = 1;
        while(radix<get_max_radix(A))
            radix*=10; // 요소 중 최댓값의 자릿수 확인

        Calendar before = Calendar.getInstance();
        for(int i=1; i<radix; i*=10){
            for(int j=0; j<A.length; j++){
                int p = (A[j]/i)%10; // 각 숫자의 자릿수(작은 자릿수부터)
                bucket[(A[j]/i)%10].offer(A[j]);
            }
            int index = 0;
            for(int k=0; k<10; k++){
                while(bucket[k].size() != 0){
                    A[index] = (int) bucket[k].peekFirst();
                    bucket[k].pollFirst();
                    index++;
                }
            }
            // radix 별 정렬
            System.out.println(i + "의 자리 정렬 []");
            for(int t=0; t<A.length; t++){
                if(t%10==0) System.out.println();
                System.out.print(A[t] + "\t");
            }
            System.out.println("\n");
        }
        Calendar after = Calendar.getInstance();

        for(int i=0; i<A.length; i++)
            result[i] = A[i];

        // 정렬 후 최종 result 배열 출력
        System.out.println("result[]");
        for(int i=0; i<result.length; i++){
            if(i%10==0) System.out.println();
            System.out.print(result[i] + "\t");
        }
        System.out.println("\n");

        int time = after.get(Calendar.MILLISECOND) - before.get(Calendar.MILLISECOND);
        System.out.println("걸린 시간 : " + time + "ms");
    }
}