기수정렬(Radix Sort)

1,10,100... 등 각 자리수를 기준으로 비교없이 정렬을 수행하는 정렬 알고리즘

https://sexycoder.tistory.com/74

1. 각 원소들 중 최대 자리수를 구한다. [1,2,3,10,157] 이라면 157, 세자릿수인 3이 최대 자리수가 된다.
2. 0 ~ 9까지의 Queue를 만든다.
3. 각 원소별 자리수의 숫자를 해당하는 번호의 Queue에 집어 넣는다.
4. 0 ~ 9 까지의 Queue를 순회하며 원소를 뽑아 기존 배열에 교체해준다.
5. 최대 자리수만큼 2 ~ 4를 반복해준다.

 

시간복잡도

최대자릿수 d만큼 반복하며 원소의 개수 n만큼 돌게 되므로 O(dn) 이므로 O(n)의 시간복잡도를 가지게 된다.

 

공간복잡도

기존원소 배열 크기 n에 추가적으로 자리수 Queue배열이 추가되므로 O(n)

 

왜 잘 안쓰지?

시간복잡도 O(n)이라는 빠른 속도를 가지고 있는데 범용적으로 잘 쓰이지 못하고 O(nlogn)의 시간복잡도를 가진 퀵정렬에 밀린다.

자리수를 기준으로 정렬을 하는 방식이기 때문에 음수나, 소수점과 같은 숫자를 정렬하지 못하고 정수여야 한다는 제약조건이 있기 때문에 범용적으로 사용되지 못한다.

 

Code

import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayList;
import java.util.List;

class Main {
    public static void main(String[] args) {
      int[] data = {7,7,3,2,1,8,9,10,10,7};
      int[] sortedArr = radixSort(data);
      for (int number : sortedArr) {
        System.out.println(number);
      }
    }

    public static int[] radixSort(int[] data) {
      int maxDigit = getMaxDigit(data);

      List<Queue<Integer>> bucket = new ArrayList<>();
      for (int i = 0; i < 10; i++) {
        Queue<Integer> q = new LinkedList<>();
        bucket.add(q);
      }

      for (int digit = 0; digit < maxDigit; digit++) {
        for (int number : data) {
          int bucketIdx = (int)(number / (int)Math.pow(10, digit))%10;
          bucket.get(bucketIdx).add(number);
        }
        int dataIdx = 0;
        for (int i = 0; i < 10; i++) {
          Queue<Integer> q = bucket.get(i);
          int qSize = q.size();
          for (int j = 0; j < qSize; j++) {
            data[dataIdx] = q.poll();
            dataIdx++;
          }
        }
      }
      return data;
    }

    private static int getMaxDigit(int[] numbers) {
      int maxDigit = 0;
      for (int number : numbers) {
        int digit = (int)Math.log10((double)number)+1;
        if (digit > maxDigit) {
          maxDigit = digit;
        }
      }
      return maxDigit;
    }
}


/*
결과
1 2 3 7 7 7 8 9 10 10
*/