[정렬] 기수정렬

정렬

정렬 알고리즘	정의	시간복잡도
삽입	대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식	O(N) ~ O(N^2)
버블	데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식	O(N^2)
선택	대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식	O(N^2)
퀵	pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식	O(NlogN) ~ O(N^2)
힙	이진트리를 이용하여 최대힙(오름차순)/최소힙(내림차순) 트리를 구성해 정렬하는 방식	O(NlogN)
병합	이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식	O(NlogN) + 추가적인 메모리 필요
기수	데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식	O(N) + 추가적인 메모리 필요

기수정렬이란?

값을 비교하지 않는 특이한 정렬
자릿수를 이용하여, 해당 자릿수의 숫자를 기록한 후 정렬된 영역에 삽입 ( 기록을 할때에는 정렬된 채로 들어가지는 않는다 )
시간복잡도는 O(kN)이며, k는 데이터의 자릿수를 의미한다

기수정렬 방식

• 자릿수별로 Queue를 이용하여, 정렬하고 이후 정렬될 숫자의 최대 자릿수만큼 반복하며 정렬하는 방식
• 시간복잡도 : O(KN) , K는 최대 자릿수

정렬 수 :	60	12	20	45	30	75	32	88	99
30 20 60		32 12			75 45			88	99
0	1	2	3	4	5	6	7	8	9
일의 자리 정렬 :	60	20	30	12	32	45	75	88	99
	12	20	32 30	45		60	75	88	99
0	1	2	3	4	5	6	7	8	9
십의 자리  정렬 :	12	20	30	32	45	60	75	88	99

• 일의 자릿수 끝났을 때 -> 일의자리수 정렬이 되있음 (따라서, 60 - 20 - 30 은 일의자리만 비교했기에, 정렬이 되지 않은상태로 저장)
• 십의 자릿수 끝났을 때 -> 십의자리 + 일의자리 정렬이 되있음
• 백의 자리수 끝났을 때 -> 백의자리 + 십의자리 + 일의자리 정렬이 되있음

 

기수정렬 구현

 

• 합배열을 이용한 정리

public class App {

    public static void radixSort(int[] arr){
        
        int[] output = new int[arr.length];

        int max = getMax(arr);
        int exp = 1;
        while(max/exp > 1){
            
            int[] sumArray = new int[10];

            //자릿수에 맞춰서 저장
            for(int i = 0; i< arr.length; i++){
                sumArray[(arr[i]/exp)%10]++;
            }

            //합 배열 구하기
            for(int i = 1; i<10; i++){
                sumArray[i] += sumArray[i-1];
            }
            
            // output에 저장하는 인덱스가 해당 범위의 끝부터 저장하기에 큰수부터 넣어야한다 (그래서 반복문을 arr.length-1부터)
            for(int i = arr.length-1; i >= 0 ; i--){
                int digit = (arr[i]/exp)%10;
                output[sumArray[digit] - 1] = arr[i];
                sumArray[digit]--;
            }


            for(int i = 0; i<arr.length; i++){
                arr[i] = output[i];
            }
            
            exp = exp*10;
        }
    }

    private static int getMax(int[] arr){
        int max = 0;
        for (int i : arr) {
            if (max < i){
                max = i;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[] array = {170, 45, 75, 90, 802, 24, 2, 66};
        radixSort(array);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }
    
}