기수(radix) 정렬

• 어떤 기수 r을 이용하여 정렬 키를 몇 개의 숫자로 분해

  • r=10 : 키를 십진수로 분할
  • r=2 : 키를 이진수로 분할

• 기수-r 정렬에서는 r개의 빈(bin)이 필요

  • 정렬되어야 하는 레코드가 R1,,,Rn일 때, 레코드의 키는 기수-r을 이용하여 분할 -> 0~(r-1) 사이의 d자리 키가 된다
  • 각 빈의 레코드는 빈의 첫 레코드를 가리키는 포인터와 마지막 레코드를 가리키는 포인터를 통해 체인으로 연결되며, 체인은 큐처럼 동작

• 기수 정렬은 정렬 순서상 앞서고 뒤섬의 판단을 위한 비교연산을 하지 않음

• 정렬 대상의 모든 길이가 동일해야 가장 효율적
  
  ※ 좋은 예) [123, 486, 309, 944], [blue, rice, pain, book] 등등
  
  ※ 나쁜 예) [5643, -43, 1, 87912], [sky, pencil, water, a] 등등
  

• 길이가 각각 다를경우 빈 공간을 메꿔야하는 추가 작업 발생 → 성능 저하

• 정렬 대상의 자리수를 기준으로 '버킷'이라는 공간에 '큐(Queue)' 방식으로 저장 후 다시 꺼냄

• 성능이 키의 크기와 r의 선택에 영향을 받음

• 정렬할 숫자들을 '버킷' 공간에 각 숫자와 동일한 위치에 저장

• '버킷' 공간에 저장된 숫자들을 처음부터 다시 꺼내어 정렬 공간에 차례대로 저장

  ※ 버킷 공간의 크기는 숫자 길이와 동일

MSD(most-significant-digit-first) 정렬

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

숫자 '134, 224, 232, 122'를 오름차순으로 정렬

LSD(least-significant-digit-first) 정렬

• 최소 유효 숫자 우선 정렬
  • '가장 작은 자릿수'부터 정렬을 진행
    • 가장 오른쪽부터(숫자로 치면 1의 자리수부터)

• LSD가 MSD보다 더 단순
  • 생성된 파일과 서브 파일을 독립적으로 정렬할 필요가 없으므로 오버헤드가 적게 든다

숫자 '134, 224, 232, 122'를 오름차순으로 정렬

구현

import java.util.Arrays;

public class Main{

    static final int N = 10;

    public static void main(String[] args) {

        int[] arr = new int{134, 224, 232, 122};

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

    public static void radixSort(int[] array) {
        final int MAX_LENGTH = getMaxLength(array), myArrLen = array.length;
        int myRadix = 1;
        int[] sortedArray = new int[myArrLen], counts;
        for (int p = 0; p < MAX_LENGTH; p++) {
            counts = new int[10];
            for (int numOfTemp : array) {
                counts[(numOfTemp / myRadix) % 10]++;
            }
            for (int i = 1; i < 10; i++)
                counts[i] += counts[i - 1];
            for (int i = myArrLen - 1; i >= 0; i--) {
                sortedArray[counts[(array[i] / myRadix) % 10]-- - 1] = array[i];
            }
            array = sortedArray;
            sortedArray = new int[myArrLen];
            myRadix *= 10;
        }
        System.out.println("정렬 후 : " + Arrays.toString(array));
    }
    public static int getMaxLength(int[] array) {
        int max = 0;
        for (int numOfTemp : array) {
            if (max < numOfTemp)
                max = numOfTemp;
        }
        return (int) Math.log10(max) + 1;
    }
}

reference

• 고려대학교 김상곤 교수님 강의 중
• [ch 10-2] 복잡하지만 효율적인 정렬 알고리즘_3(기수 정렬)
• 기수 정렬(Radix Sort)