기수 정렬 (Radix sort)

기수 정렬 (Radix Sort)

기수 정렬은 값을 비교하지 않는 특이한 정렬이다. 기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교한다. 시간 복잡도는 O(kn)으로, 여기서 k는 데이터의 자릿수를 말한다.

(예를 들어 234, 123을 비교하면 4와 3, 2과 2, 2와 1만 비교한다.)

 

기수 정렬은 10개의 큐를 이용한다. 각 큐는 값의 자릿수를 대표한다. 

 

https://www.geeksforgeeks.org/c-program-for-radix-sort/

 

수행 방식은 다음과 같다.

일의 자릿수 기준으로 배열 원소를 큐에 집어넣는다. 0번째 큐부터 9번째 큐까지 차례대로 pop을 진행하면 1의 자릿수에 맞게 정렬이 된다. 이어서 십의 자릿수를 기준으로 같은 과정을 진행한다. 마지막 자릿수를 기준으로 정렬할 때까지 앞의 과정을 반복한다. 

 

기수 정렬은 O(kn)으로 시간 복잡도가 가장 짧은 정렬이다. 그러나 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요하다.

 

---

 

[백준 10989번] 수 정렬하기3

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

 

[정답]

import java.io.*;
import java.util.*;

public class Main {
    public static int[] A;
    public static long result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = Integer.parseInt(br.readLine());
        }
        br.close();
        RadixSort(A, 5);
        for (int i = 0; i < N; i++) {
            bw.write(A[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    public static void RadixSort(int[] A, int max_size) {
        int[] output = new int[A.length];
        int jarisu = 1;
        int count = 0;
        while(count != max_size) {      // 최대 자릿수만큼 반복
            int[] bucket = new int[10];
            for (int i = 0; i < A.length; i++) {
                bucket[(A[i] / jarisu) % 10]++;     // 일의 자리부터 시작하기
            }
            for (int i = 1; i < 10; i++) {      // 합 배열을 이용해 index 계산하기
                bucket[i] += bucket[i-1];
            }
            for (int i = A.length - 1; i >= 0; i--) {   // 현재 자릿수를 기준으로 정렬하기
                output[bucket[(A[i] / jarisu % 10)] - 1] = A[i];
                bucket[(A[i] / jarisu) % 10]--;
            }
            for (int i = 0; i < A.length; i++) {
                // 다음 자릿수를 이동하기 위해 현재 자릿수 기준 정렬 데이터 저장하기
                A[i] = output[i];
            }
            jarisu *= 10;   // 자릿수 증가시키기
            count++;
        }
    }
}

 

 

일반적인 기수 정렬은 우선순위 큐를 사용해 비교적 간단하게 구하는 방법이 있지만 시간 복잡도를 느리게 하는 요소가 있으므로 위 코드와 같이 구간 합을 이용하는 방법으로 구현하였다. 큐를 이용한 방법의 코드는 아래와 같다.

 

public class RadixSort {
    private static int[] A = { 38, 27, 43, 9, 3, 82, 10 };
    private static final int BUCKET_SIZE=10; //자릿수는 0~9까지가 최대이므로, bucket 사이즈는 10
    
    public static void main(String[] args) {
        System.out.println("정렬 전: " + Arrays.toString(A));
        radixSort(A.length);
        System.out.println("정렬 후: " + Arrays.toString(A));
    }
    
    public static void radixSort(int len) {
        Queue<Integer>[] bucket = new LinkedList[BUCKET_SIZE];
        for(int i=0; i<BUCKET_SIZE; i++) {
            bucket[i] = new LinkedList<>();
        }
        
        // 정렬할 자릿수의 크기 만큼 반복한다.
        // 현재 배열의 가장 큰 수는 10의 자리이므로, 2번 반복하게 한다.
        int m = 1;
        for(int d=0; d<2; d++) {
            for(int i=0; i<len; i++) {
                bucket[(A[i]/m)%10].add(A[i]);
            }
            
            for(int i=0, j=0; i<BUCKET_SIZE; i++) {
                while(!bucket[i].isEmpty()) {
                    A[j++] = bucket[i].poll();
                }
            }
            m *= 10;
        }
    }
}

 

 

 

 

[참고자료]

- 알고리즘 코딩 테스트 자바편

- https://www.geeksforgeeks.org/radix-sort/

Radix Sort - Data Structures and Algorithms Tutorials - GeeksforGeeks

- https://lktprogrammer.tistory.com/48

06 정렬 알고리즘 - 기수 정렬(Radix Sort)

- https://kind-coding.tistory.com/227

기수 정렬 (Radix Sort)