[알고리즘] 기수 정렬(Radix Sort)

joyful·2024년 4월 9일

Algorithm

목록 보기

62/62

1. 개념

입력값을 자릿수별로 구분해서 부분적으로 비교하여 정렬하는 방식

주어진 데이터의 값을 자릿수별로 나누고, 각 자릿수에 대해 계수 정렬과 같은 안정적인 정렬 알고리즘을 적용하여 정렬

2. 과정

2-1. LSD(Least Significant Digit)

낮은 자리부터 높은 자리로 진행(Right-to-Left)

가장 낮은 자릿수(일의 자리)부터 시작하여 가장 높은 자릿수로 이동하며 정렬을 수행한다.
입력 배열을 순회하며 각 자릿수에 해당하는 값을 보조 배열에 기록한다. 이때 보조 배열의 인덱스는 각 자릿수의 값(0 ~ 9)을 나타내고, 해당 인덱스에는 해당 자릿수의 값이 등장한 횟수가 저장된다.
보조 배열을 순회하면서 각 값의 누적 등장 횟수를 계산한다. 이는 정렬된 배열에서 해당 값이 위치해야 할 인덱스를 나타낸다.
입력 배열을 역순으로 순회하면서 각 자릿수에 해당하는 값을 보조 배열을 참조하여 정렬된 배열에 값을 배치한다.
보조 배열을 참조하여 정렬된 배열에 값을 배치하고, 동일한 값에 대해서는 누적 등장 횟수를 감소시킨다.
가장 낮은 자릿수부터 가장 높은 자릿수까지의 정렬을 반복하여 수행한다.
모든 자릿수에 대한 정렬이 완료되면 정렬된 배열을 반환한다.

2-2. MSD(Most Significant Digit)

높은 자리부터 낮은 자리로 진행(Left-to-Right)

가장 높은 자릿수(가장 큰 자릿수)부터 시작하여 가장 낮은 자릿수로 이동하며 정렬을 수행한다.
입력 배열을 순회하며 각 자릿수에 해당하는 값을 보조 배열에 기록한다. 이때 보조 배열의 인덱스는 각 자릿수의 값(0 ~ 9)을 나타내고, 해당 인덱스에는 해당 자릿수의 값이 등장한 횟수가 저장된다.
보조 배열을 순회하면서 각 값의 누적 등장 횟수를 계산한다. 이는 정렬된 배열에서 해당 값이 위치해야 할 인덱스를 나타낸다.
입력 배열을 역순으로 순회하면서 각 자릿수에 해당하는 값을 보조 배열을 참조하여 정렬된 배열에 값을 배치한다.
보조 배열을 참조하여 정렬된 배열에 값을 배치하고, 동일한 값에 대해서는 누적 등장 횟수를 감소시킨다.
가장 높은 자릿수부터 가장 낮은 자릿수까지의 정렬을 반복하여 수행한다.
모든 자릿수에 대한 정렬이 완료되면 정렬된 배열을 반환한다.

3. 구현

3-1. LSD(Least Significant Digit)

import java.util.Arrays;

public class RadixSort {
	/**
	 * 기수 정렬 메서드
	 */
	public static void radixSort(int[] array) {
    	// 입력 배열의 최대값 찾기
        int max = Arrays.stream(array).max().getAsInt();
        
        // 최댓값의 자릿수 구하기
        int maxDigit = (int) Math.log10(max) + 1;
        
        for (int exponent = 1; exponent <= maxDigit; exponent++) {
        	countingSort(array, exponent);
        }
    }
    
    /**
	 * 기수에 따라 배열을 정리하는 메서드
	 */
    private static void countingSort(int[] array, int exponent) {
    	int length = array.length;
        int[] output = new int[length];
        int[] count = new int[10];	// 자릿수(0~9)를 처리하기 위한 카운트 배열
        
        // 각 자릿수별로 개수 세기
        for (int index = 0; index < length; index++) {
        	int digit = (array[index] / exponent) % 10;
            count[digit]++;
        }
        
        // count 배열을 업데이트하여 각 값의 누적 등장 횟수 계산
        for (int index = 1; index < 10; index++) {
        	count[index] += count[index - 1];
        }
        
        // output 배열 생성
        for (int index = length - 1; index >= 0; index--) {
        	int digit = (array[index] / exponent) % 10;
            output[count[digit] - 1] = array[index];
            count[digit]--;
        }
        
        // output 배열을 array에 복사
        System.arraycopy(output, 0, array, 0, length);
    }
    
    /**
	 * 배열 출력 메서드
	 */
    public static void printArray(int[] array) {
    	System.out.println(Arrays.toString(array));
    }
    
    public static void main(String[] args) {
    	int[] array = {170, 45, 75, 90, 802, 24, 2, 68};
        System.out.print("기수 정렬 전 배열 : ");
        printArray(array);
        
        radixSort(array);
        
        System.out.print("기수 정렬 후 배열 : ");
        printArray(array);
    }
}

3-2. MSD(Most Significant Digit)

import java.util.Arrays;

public class RadixSort {
	/**
	 * 기수 정렬 메서드
	 */
	public static void radixSort(int[] array) {
    	int max = Arrays.stream(array).max().getAsInt();
        radixSort(array, 0, array.length - 1, max);
    }
    
    /**
	 * 기수 정렬 재귀 메서드
	 */
    private static void radixSort(int[] array, int low, int high, int exponent) {
    	if (low >= high || exponent <= 0) {
        	return;
        }
        
        int[] output = new int[array.length];
        int[] count = new int[10];
        
        // 각 자릿수별로 개수 세기
        for (int index = low; index <= high; index++) {
        	int digit = (array[index] / exponent) % 10;
            count[digit]++;
        }
        
        // count 배열을 업데이트하여 각 값의 누적 등장 횟수 계산
        for (int index = 1; index < 10; index++) {
        	count[index] += count[index - 1];
        }
        
        // output 배열 생성
        for (int index = high; index >= low; index--) {
        	int digit = (array[index] / exponent) % 10;
            output[count[digit] - 1] = array[i];
            count[digit]--;
        }
        
        // output 배열을 array에 복사
        System. arraycopy(output, 0, array, low, high - low + 1);
        
        // 각 자릿수별로 재귀적으로 기수 정렬 수행
        for (int index = 0; index < 10; index++) {
        	radixSort(array, low + count[index], low + count[index + 1] - 1, exponent / 10);
        }
    }
    
    /**
	 * 배열 출력 메서드
	 */
    public static void printArray(int[] array) {
    	System.out.println(Arrays.toString(array));
    }
    
    public static void main(String[] args) {
    	int[] array = {170, 45, 75, 90, 802, 24, 2, 68};
        System.out.print("기수 정렬 전 배열 : ");
        printArray(array);
        
        radixSort(array);
        
        System.out.print("기수 정렬 후 배열 : ");
        printArray(array);
    }
}

4. 성능 분석

4-1. LSD(Least Significant Digit)

/**
 * 기수 정렬 메서드
 */
public static void radixSort(int[] array) {
    // 입력 배열의 최대값 찾기 : O(n)
    int max = Arrays.stream(array).max().getAsInt();
    
    // 최댓값의 자릿수 구하기 : O(1)
    int maxDigit = (int) Math.log10(max) + 1;
    
    for (int exponent = 1; exponent <= maxDigit; exponent++) {
    	countingSort(array, exponent);
    }
}

/**
 * 기수에 따라 배열을 정리하는 메서드
 */
private static void countingSort(int[] array, int exponent) {
	int length = array.length;
    int[] output = new int[length];
    int[] count = new int[10];
    
    // 각 자릿수별로 개수 세기 : O(n)
    for (int index = 0; index < length; index++) {
    	int digit = (array[index] / exponent) % 10;
        count[digit]++;
    }
    
    // count 배열을 업데이트하여 각 값의 누적 등장 횟수 계산 : O(k)
    for (int index = 1; index < 10; index++) {
    	count[index] += count[index - 1];
    }
    
    // output 배열 생성 : O(n)
    for (int index = length - 1; index >= 0; index--) {
    	int digit = (array[index] / exponent) % 10;
        output[count[digit] - 1] = array[index];
        count[digit]--;
    }
    
    // output 배열을 array에 복사 : O(n)
    System.arraycopy(output, 0, array, 0, length);
}

최대값 및 자릿수 찾기 : O(n) + O(1) = O(n)
기수별 정렬 : O(n + k + n) = O(2n + k)
전체 시간 복잡도 : O(n) + O(2n + k) = O(3n + K) => O(n)

4-2. MSD(Most Significant Digit)

/**
 * 기수 정렬 메서드
 */
public static void radixSort(int[] array) {
	int max = Arrays.stream(array).max().getAsInt();	// O(n)
    radixSort(array, 0, array.length - 1, max);
}

/**
 * 기수 정렬 재귀 메서드
 */
private static void radixSort(int[] array, int low, int high, int exponent) {
	if (low >= high || exponent <= 0) {
    	return;
    }
    
    int[] output = new int[array.length];
    int[] count = new int[10];
    
    // 각 자릿수별로 개수 세기 : O(n)
    for (int index = low; index <= high; index++) {
    	int digit = (array[index] / exponent) % 10;
        count[digit]++;
    }
    
    // count 배열을 업데이트하여 각 값의 누적 등장 횟수 계산 : O(k)
    for (int index = 1; index < 10; index++) {
    	count[index] += count[index - 1];
    }
    
    // output 배열 생성 : O(n)
    for (int index = high; index >= low; index--) {
    	int digit = (array[index] / exponent) % 10;
        output[count[digit] - 1] = array[i];
        count[digit]--;
    }
    
    // output 배열을 array에 복사 : O(n)
    System. arraycopy(output, 0, array, low, high - low + 1);
    
    // 각 자릿수별로 재귀적으로 기수 정렬 수행 : O(k)
    for (int index = 0; index < 10; index++) {
    	radixSort(array, low + count[index], low + count[index + 1] - 1, exponent / 10);
    }
}

최대값 및 자릿수 찾기 : O(n) + O(1) = O(n)
기수별 정렬 : O(kn) (총 k번 순회)
전체 시간 복잡도 : O(n) + O(kn) = O(n + kn) => O(n)

5. 특징

입력 데이터의 자릿수가 상수일 때 유용하다.
- d 자릿수 n개의 숫자들에 대해 계수 정렬을 적용하면 O(dn)
  → 여기서 d를 입력 크기 n과 무관한 상수로 간주하면 O(n)
안정적 정렬 알고리즘이다.
- 각 자릿수별로 안정적인 계수 정렬 알고리즘을 적용하므로, 기수 정렬 역시 안정적
제자리 정렬 알고리즘이 아니다.
- 계수 정렬을 적용하므로, 전체 데이터 개수와 진법 크기 만큼의 추가 공간이 필요

📖 참고

이관용, 김진욱(2024). 알고리즘. 한국방송통신대학교출판문화원

joyful

기쁘게 코딩하고 싶은 백엔드 개발자

이전 포스트

[알고리즘] 기수 정렬(Radix Sort)

Algorithm

1. 개념

2. 과정

2-1. LSD(Least Significant Digit)

2-2. MSD(Most Significant Digit)

3. 구현

3-1. LSD(Least Significant Digit)

3-2. MSD(Most Significant Digit)

4. 성능 분석

4-1. LSD(Least Significant Digit)

4-2. MSD(Most Significant Digit)

5. 특징

[알고리즘] 계수 정렬(Counting Sort)

0개의 댓글