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

기수 정렬(Radix Sort)

값을 비교하지 않는 특이한 정렬
값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교
낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘
-> 자릿수가 안맞으면 자릿수를 맞춰주는 작업을 먼저 해야한다.

시간 복잡도

O(kn)
k = 데이터의 자릿수
-> 예) 234, 123 비교시 4와3, 3과 2, 2와 1만 비교

핵심 이론

10개의 큐를 이용!
각 큐 = 각 자릿수의 값을 대표

1. 일의 자릿수 (0~9)를 나타내는 10개의 큐 : 일의 자릿수를 기준으로 배열원소를 큐에 집어넣음
2. 0~9번째 큐까지 pop을 진행. -> 일의 자리에서 정렬된 순서 기준으로 십의 자리에 저장하는 것이 중요!!
3. 십의 자릿수 (0~9)를 나타내는 10개의 큐 : 십의 자릿수를 기준으로 배열원소를 큐에 집어넣음
   ....
4. 마지막 자릿수(가장 큰 자릿수)를 기준으로 정렬할 때까지 앞 과정 반복

예시

주어진 데이터와 큐 10개

1의 자리에 대해 수행

큐 0부터 값을 빼온 결과 : 일차적으로 정렬

10의 자리에 대해 수행

최종 정렬 완료

특징

• 자리수가 고정되어 있어서 안정성이 있는 정렬 방식

• 공간 낭비를 덜기위해, 크기를 미리 할당하는 배열이 아닌 리스트를 이용하자!

구현

import java.util.LinkedList;
import java.util.Queue;

public class RadixBasic {
    // 10진수 기준으로 구현
    private static int BUCKET_NUM = 10;

    public static void sort(int[] arr) {
        // 10진수 버킷 생성
        Queue<Integer>[] bucket = new LinkedList[BUCKET_NUM];
        for(int i=0; i<BUCKET_NUM; i++) {
            bucket[i] = new LinkedList<>();
        }

        int maxLen = maxDigitCount(arr);
        // 각 자리수의 숫자 저장
        int digitNumber = 0;
        // 배열에 다시 저장할 때 필요한 변수
        int arrIndex = 0;

        // 자리수만큼 반복
        for(int i=0; i<maxLen; i++) {
            // 데이터의 개수만큼 반복
            for(int j=0; j<arr.length; j++) {
                digitNumber = getDigit(arr[j], i);

                bucket[digitNumber].add(arr[j]);
            }

            // 버킷에 들어간 데이터를 순서대로 꺼내 배열에 덮어씌움
            for(int j=0; j<BUCKET_NUM; j++) {
                while (!bucket[j].isEmpty()) {
                    arr[arrIndex++] = bucket[j].remove();
                }
            }
            arrIndex = 0;
        }
    }

    // 숫자의 자리수 반환
    // getDigit(123, 0) => 3
    // getDigit(123, 1) => 2
    // getDigit(123, 2) => 1
    private static int getDigit(int num, int index) {
        return (int)Math.floor(Math.abs(num) / Math.pow(10, index)) % 10;
    }

    // 숫자의 자리수 구하기
    // digitCount(10) => 2
    // digitCount(1) => 1
    // digitCount(1000) => 4
    private static int digitCount(int num) {
        if (num == 0) {
            return 1;
        }

        // log10을 하면 자리수가 나옴
        // log10(10) => 1
        // log10(100) -> log10(10^2) => 2
        return (int)Math.floor(Math.log10(Math.abs(num))) + 1;
    }

    // 데이터들 중 가장 큰 자리수 반환
    private static int maxDigitCount(int[] arr) {
        int max = 0;

        for(int i=0; i<arr.length; i++) {
            max = Math.max(max, digitCount(arr[i]));
        }

        return max;
    }
}

참고
https://banjjak1.tistory.com/52