개발자로 살아남기

기수 정렬 (Radix Sort)

기수 정렬 (Radix Sort)

• 비교 연산이 없는 정렬 알고리즘
• 적용할 수 있는 범위가 제한적임
   - 정수, 알파벳, 특수문자 등의 아스키로 표현할 수 있는 것들
   - 소수는 불가능
• 기수 (Radix)를 이용한 정렬
   - 2진수의 경우 : 0, 1   /   10진수의 경우 : 0 ~ 9   /   알파벳 소문자의 경우 : a ~ z (0 ~ 25)
• 기수만큼의 추가 저장 공간이 필요함
   - 저장 공간을 버킷 (Bucket) 이라고 부름
• Queue를 이용한 정렬 알고리즘
• LSD (Least Significant Digit) 정렬 방법과 MSD (Most Significant Digit) 정렬 방법이 있음
   - LSD : 덜 중요한 첫번째 자리수부터 정렬 (즉, 가장 작은 자리수)
      ex) 1234 일 경우 4부터 정렬
   - MSD : 가장 중요한 마지막 자리수부터 정렬 (즉, 가장 큰 자리수)
      ex) 1234 일 경우 1부터 정렬
      MSD의 경우 구현의 난이도가 높으며 중간에 데이터를 확인해야 하는 단점이 있음
• 안정 정렬 (Stable Sort)
   - 동일한 데이터의 순서가 정렬 후에도 변함이 없음
  ex) 5(A), 5(B), 3, 2, 1 => 1, 2, 3, 5(A), 5(B)
• 비 제자리 정렬 (out of place)
   - 정렬 시 추가적인 저장공간(버킷)이 필요하므로 제자리 정렬이 아님

기수정렬 방법

1. 기수만큼 큐(Queue)를 이용해 저장공간 (Bucket)을 생성한다.
2. 데이터의 1의 자리를 기준으로 버킷에 넣는다.
3. 버킷에 저장된 데이터를 순서대로 꺼내 기존 데이터에 덮어쓴다.
4. 데이터의 10의 자리를 기준으로 버킷에 넣는다.
5. 마지막 자리수까지 정렬의 기준이 될 자리수를 늘리며 정렬한다.
   
   

   

성능

• 비교연산이 아닌 데이터 삽입과 추출의 빈도수로 성능을 평가함
• 길이가 가장 긴 자리수를 k, 데이터 개수를 n 이라고 했을 때, k 자리수 까지의 반복과 데이터 n개를 반복해서 정렬하므로 k * n 이 된다.
• 최악의 경우 : O(kn)
• 최선의 경우 : O(kn)

구현

• LSD로 구현
  [RadixBasic.java]
  

  package Sort.Radix;
  
  import java.util.LinkedList;
  import java.util.Queue;
  
  public class RadixBasic {
      // 10진수 기준으로 구현
      private static int BUCKET_NUM = 10;
  
      public static void sort(int[] arr) {
          // 10진수 버킷 생성
          Queue<Integer>[] bucket = new LinkedList[BUCKET_NUM];
          for(int i=0; i<BUCKET_NUM; i++) {
              bucket[i] = new LinkedList<>();
          }
  
          int maxLen = maxDigitCount(arr);
          // 각 자리수의 숫자 저장
          int digitNumber = 0;
          // 배열에 다시 저장할 때 필요한 변수
          int arrIndex = 0;
  
          // 자리수만큼 반복
          for(int i=0; i<maxLen; i++) {
              // 데이터의 개수만큼 반복
              for(int j=0; j<arr.length; j++) {
                  digitNumber = getDigit(arr[j], i);
  
                  bucket[digitNumber].add(arr[j]);
              }
  
              // 버킷에 들어간 데이터를 순서대로 꺼내 배열에 덮어씌움
              for(int j=0; j<BUCKET_NUM; j++) {
                  while (!bucket[j].isEmpty()) {
                      arr[arrIndex++] = bucket[j].remove();
                  }
              }
              arrIndex = 0;
          }
      }
  
      // 숫자의 자리수 반환
      // getDigit(123, 0) => 3
      // getDigit(123, 1) => 2
      // getDigit(123, 2) => 1
      private static int getDigit(int num, int index) {
          return (int)Math.floor(Math.abs(num) / Math.pow(10, index)) % 10;
      }
  
      // 숫자의 자리수 구하기
      // digitCount(10) => 2
      // digitCount(1) => 1
      // digitCount(1000) => 4
      private static int digitCount(int num) {
          if (num == 0) {
              return 1;
          }
  
          // log10을 하면 자리수가 나옴
          // log10(10) => 1
          // log10(100) -> log10(10^2) => 2
          return (int)Math.floor(Math.log10(Math.abs(num))) + 1;
      }
  
      // 데이터들 중 가장 큰 자리수 반환
      private static int maxDigitCount(int[] arr) {
          int max = 0;
  
          for(int i=0; i<arr.length; i++) {
              max = Math.max(max, digitCount(arr[i]));
          }
  
          return max;
      }
  }​

• 테스트
  [RadixBasicMain.java]
  

  package Sort.Radix;
  
  public class RadixBasicMain {
      private static final int MAX_COUNT = 30;
  
      public static void main(String[] args) {
          int[] arr = new int[MAX_COUNT];
          for(int i=0; i<MAX_COUNT; i++) {
              // 0 ~ MAX_COUNT 범위내의 난수를 생성
              arr[i] = (int)(Math.random() * MAX_COUNT);
          }
  
          System.out.println("정렬 전 데이터");
          for(int i : arr) {
              System.out.print(i + " ");
          }
          System.out.println();
  
          System.out.println("정렬 후 데이터 (오름차순)");
          int[] radixSortTestArray = arr.clone();
          RadixBasic.sort(radixSortTestArray);
          for(int i : radixSortTestArray) {
              System.out.print(i + " ");
          }
          System.out.println();
  
      }
  }​

• 결과
  

  

참고

윤성우의 열혈 자료구조

https://ko.wikipedia.org/wiki/%EA%B8%B0%EC%88%98_%EC%A0%95%EB%A0%AC

https://www.geeksforgeeks.org/radix-sort/