[JAVA] 기수정렬(Radix Sort) 개념과 코드 구현

기수(자릿수)별로 비교 없이 수행하는 정렬 알고리즘이다.

기수에 따라 원소를 버킷에 집어넣기때문에 비교 연산이 불필요하다.

해당 과정을 일의자리부터 가장 큰 자릿수까지 반복하면서 정렬한다. 각 자릿값에 대해 계수정렬을 수행한다.

데이터 크기에 비례하여 추가적인 메모리 공간이 많이 필요하다는 단점이 있다.

구분	최악 시간복잡도	최선 시간복잡도	평균 시간복잡도	공간복잡도(메모리)	안정성
기수정렬	O(d *(n+k))	O(d*(n+k))	O(d*(n+k))	O(n+k)	Y

* d: 가장 큰 자릿수의 수, n: 데이터의 개수, k: 버킷의 개수

 

알고리즘

1. 정렬할 데이터 중 가장 큰 자릿수를 구한다.

2. 데이터의 일의 자리부터 가장 큰 자릿수까지 자릿수 별로 정렬을 수행한다.

3. 각 자릿수 별로 정렬하기 위해 0부터 9까지의 버킷(바구니)을 사용한다.

4. 일의 자리부터 가장 큰 자릿수까지 차례대로 각 자릿수에 해당하는 숫자를 세고 해당 버킷에 데이터를 넣는다.

5. 버킷에 넣은 데이터를 순서대로 꺼내어 원래 데이터 배열에 다시 저장한다.

6. 위 과정을 큰자릿수까지 반복한다.

 

소스코드

public static int[] radixSort(int[] arr) {
    // 최대값을 먼저 구한다. (최대 자릿수 구하기 위해)
    int maxValue = arr[0];
    for (int i = 1; i < arr.length; i++) {
        if (maxValue < arr[i]){
            maxValue = arr[i];
        }
    }

    // Counting Sort를 사용하여 자릿수 기준으로 정렬한다.
    // 기수정렬은 정렬할 데이터를 자릿수 기준으로 분리한 후 각 자리값에 대해 계수정렬을 수행한다.
    for (int digit = 1; digit <= maxValue; digit *= 10) {
        arr = countingSort(arr, digit);
    }
    return arr;
}

public static int[] countingSort(int[] arr, int digit) {
    int[] temp = new int[arr.length]; // 임시로 사용할 공간
    int[] counting = new int[10]; // 카운팅 배열

    for (int i = 0; i < arr.length; 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 = arr.length - 1; i >= 0; i--) {
        // 현재 배열의 자릿수를 구한다.
        int num = (arr[i] / digit) % 10;
        // 해당 자릿수를 인덱스로 counting 배열의 요소를 1씩 뺀 후,
        counting[num]--;
        // 구한 값을 인덱스로 배열의 요소를 삽입한다.
        temp[counting[num]] = arr[i];
    }
    //해당 배열을 반환한다.
    return temp;
}

참고

2023.04.17 - [추가 공부/알고리즘 & 코딩테스트] - [JAVA] 계수정렬(Counting Sort) 개념과 코드 구현