기수 정렬 (Radix Sort)

특징

• 낮은 자리 수부터 정렬하는 방식
  - ex) 123이 있으면 1의 자리수 3부터 -> 2 -> 1 순으로 정렬
• 각 원소 간의 비교 연산을 하지 않아 빠른 대신, 기수 테이블을 위한 메모리 필요
• O(dn) -> d는 최대 자리수
  - ex) [1, 2, 3, 4, 5, 1000000]이 있으면 1000000 떄문에 복잡도가 크게 늘어날 수 있다

정렬 과정

1의 자리 수에 대한 정렬

• 기수 테이블에 정렬한 이후 각 큐들을 순서대로 dequeue해서 배열에 넣는다
  
  10의 자리 수에 대한 정렬
• 위에서 정렬된 배열을 다시 한번 10의 자리 수 값들을 기준으로 정렬한다
  

소스코드

1. 기수 테이블 만들고
2. 최대 자리수를 구한 다음에
3. 자리수만큼 반복

// 기수 정렬

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
    public static void radixSort(int[] arr) {
        // 기수 테이블 생성
        ArrayList<Queue<Integer>> list = new ArrayList<>();
        for (int i = 0; i < 10; i++)
        {
            list.add(new LinkedList()); //각 숫자별로 해당 값을 담을 리스트 추가
        }

        int idx = 0;    //배열에 넣을 때 사용할 인덱스
        int div = 1;    //원하는 자리수를 가져오기 위해 나눌때 사용할 값
        int maxLen = getMaxLen(arr);
        // 자리수 만큼 기수 정렬 반복
        for (int i = 0; i < maxLen; i++)
        {
            // 각 자리수에 맞는 큐 위치에 데이터 삽입
            for (int j = 0; j < arr.length; j++) {
                list.get((arr[j] / div) % 10).offer(arr[j]);    //(arr[j] / div) % 10) 위치에 있는 리스트에 arr[j] 추가
            }

            // 다시 순서대로 가져와서 배치
            for (int j = 0; j < 10; j++) {
                Queue<Integer> queue = list.get(j); //queue에 list.get(j) 자리에 있는 리스트 넣음

                while (!queue.isEmpty()) {  //queue에 있는 것들을 arr에 넣음
                    arr[idx++] = queue.poll(); 
                }
            }

            idx = 0;    //인덱스 초기화
            div *= 10;  //다음 자리수를 기준으로 정렬하기 위해 div에 10을 곱한다
        }
    }


    //기수 테이블을 만들 때 사용하기 위한 가장 긴 자리수를 구하는 메소드
    public static int getMaxLen(int[] arr)
    {
        // 배열에 숫자들 중 가장 긴 자리수 구하기
        int maxLen = 0;
        for (int i = 0; i < arr.length; i++) {
            int len = (int)Math.log10(arr[i]) + 1;
            if (maxLen < len) {
                maxLen = len;
            }
        }
        return maxLen;
    }


    public static void main(String[] args) {
        // Test code
        int[] arr = {10, 32, 52, 27, 48, 17, 99, 56};
        radixSort(arr);
        System.out.println("기수 정렬: " + Arrays.toString(arr));
    }
}