[알고리즘] 기수 정렬

23.07.13 스터디

대수 정렬이라고도 부르며, 정렬할 데이터의 자릿수를 활용해 숫자나 문자열을 정렬하는 비교 기반 정렬 알고리즘이 아닌 정렬 방법입니다.
기수 정렬은 가장 낮은 자릿수부터 정렬을 진행하거나 가장 높은 자릿수부터 정렬하는 두 가지 방식이 있습니다. 이 두 방식은 각각 최하위 자릿수 우선(Least Significant Digit) 기수 정렬과 최상위 자릿수 우선(Most Significant Digit) 기수 정렬이라고 불립니다. 기수 정렬은 다음 과정을 통해 진행됩니다.
1. 가장 낮은 자릿수부터 시작하여 각 값을 동일한 자릿수 그룹으로 분리합니다.
2. 그룹을 차례대로 합쳐서, 다음 자릿수를 다시 그룹으로 분리합니다.
3. 이 과정을 정렬할 데이터의 가장 높은 자릿수까지 반복합니다.

• 기수(Radix)란 '주어진 데이터를 구성하는 기본 요소'를 말함
  ※ 예) 2진수의 기수: 0, 1, 10진수의 기수: 0 ~ 9

LSD, MSD

1. LSD(Least Significant Digit) 방식의 정렬

• '가장 작은 자릿수'부터 정렬을 진행
  ※ 가장 오른쪽부터 (숫자로 치면 1의 자리수부터 진행합니다.)
• 가장 작은 자릿수부터 가장 큰 자릿수까지 비교해야 된다는 단점이 존재하지만, 코드 구현은 MSD에 비해 간결하다는 장점이 있습니다.

2. MSD(Most Significant Digit) 방식의 정렬

• '가장 큰 자릿수'부터 정렬을 진행
  ※ 가장 왼쪽부터
• 코드 구현은 LSD에 비해 추가 작업(정렬 상태 확인)이 필요하지만, 중간에 정렬이 완료될 수 있는 장점이 존재

<중요>

• 기수 정렬은 정렬 순서상 앞서고 뒤섬의 판단을 위한 비교연산을 하지 않음
• 정렬 대상의 모든 길이가 동일해야 가장 효율적
  ※ 좋은 예) [123, 486, 309, 944], [blues, rices, pains, books] 등등
  ※ 나쁜 예) [56431, -43, 1, 879123], [sky, pencil, water, a] 등등
• 길이가 각각 다를경우 빈 공간을 메꿔야하는 추가 작업 발생 → 성능 저하
• 정렬 대상의 자리수를 기준으로 '버킷'이라는 공간에 '큐(Queue)' 방식으로 저장 후 다시 꺼냄

기수 정렬의 핵심이론

기수 정렬은 10개의 큐를 이용하며, 각 큐는 값의 자릿수를 대표합니다.

시간복잡도

기수 정렬의 시간 복잡도는 O(nk)입니다. 여기서 n은 데이터의 개수, k는 데이터의 최대 자릿수를 나타냅니다.

낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 알고리즘이며, 비교 연산을 하지 않아 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요한다.
각 데이터의 자릿수를 기준으로 분류하므로 가장 큰 자릿수를 D라고 했을 때 O(DN)의 시간복잡도를 갖는다.

기수 정렬은 서로 다른 자릿수와 값 범위가 작을 때 효율적입니다.
그러나 값 범위가 크거나 데이터의 자릿수가 다양한 경우, 공간 효율성과 성능이 저하될 수 있습니다.
기수 정렬은 정수, 문자열 등의 데이터에 적용할 수 있지만, 실수와 같이 자릿수가 명확하지 않은 경우에는 적용하기 어렵다는 단점이 존재합니다.

CODE

package Algorithm;

import java.util.Arrays;
import java.util.Random;

public class RadixSort {

    static final int N = 10;

    public static void main(String[] args) {
        Random random = new Random(); // 랜덤함수를 이용

        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = random.nextInt(100); // 0 ~ 99
        }

        System.out.println("정렬 전: " + Arrays.toString(arr));
        radixSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }

    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[10]; // 카운팅 배열

        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];
        }
    }

}

[gif 출처]