기수 정렬 (Radix Sort)

한유진·2021년 10월 24일

radix sort 기수 정렬 정렬알고리즘 특수정렬알고리즘

알고리즘

목록 보기

7/8

정의

가장 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 알고리즘

정렬 방법

데이터 중 가장 큰 자리수를 구한다
가장 작은 자리수부터 가장 큰 자리수까지 해당 자리수만을 보고 Counting Sort를 진행한다

코드

private static void radixSort(int[] arr) {
	//최대값 구하기
    int max = arr[0];
    for(int i = 1; i < arr.length; i++) {
    	if(max < arr[i])
        	max = arr[i];
   	}
    //Counting Sort를 사용하여 해당 자리 정렬하기
    for(int digit = 1; digit <= max; digit *= 10){
    	countingSort(arr, digit);
    }
}
private static void countingSort(int[] arr, int digit) {
	int[] temp = new int[N];
    int[] counting = new int[N]; 
    
    for(int i = 0; i < N; i++) {
    	int num = (arr[i] / digit) % 10; //해당 자리수의 숫자 추출
        counting[num]++;
    }
    
    //누적합 배열로 만들기
    for(int i = 1; i < counting.length; i++) {
    	counting[i] ++ counting[i - 1];
    }
    
    //뒤에서부터 시작 == 값이 큰것이 뒤로
    for(int i = 0; i < N; i++) {
    	int num = (arr[i] / digit) % 10;
        int index = counting[num];
        
        temp[index - 1] = arr[i];
        counting[num]--;
    }
    //복사
    for(int i = 0; i < N; i++) {
    	arr[i] = temp[i];
    }
 }