[Algorithm] 도수/계수 정렬(Counting Sort)

1. 도수 정렬(Counting Sort)이란?

• 요소의 대소 관계를 판단하지 않고 (다른 정렬 알고리즘들은 두 요소의 키 값을 비교해야 한다.) 단순하게 크기를 기준으로 세는 알고리즘이다.
• 데이터를 비교, 교환하는 작업이 없고 다중 for문이 아닌 단순 for문을 사용하고 재귀 호출과 중첩 for문이 없기 때문에 아주 효율적이다.
• 도수분포표가 필요하기 때문에 데이터의 최솟값과 최댓값을 미리 알고있을 경우, 즉 범위 조건(e.g. 5이하 자연수를 오름차순 정렬)이 있는 경우에만 사용할 수 있다. 
• 각 단계의 for문에서 배열 요소를 건너뛰지 않고 순서대로 스캔하기 때문에 같은 값의 순서가 바뀌는 일이 없다. 따라서 안정적인 정렬 알고리즘이다.
• 시간 복잡도는 O(n)으로 매우 빠르다.

이미지 출처: https://miro.medium.com/max/601/1*8cV2J9h2kJFNqOelZD_-eQ.png

2. 동작 방식

총 4단계의 for문을 수행하며 정렬한다.

1. 도수 분포표 만들기 (각각의 값을 갖는 요소가 몇개 있는지 확인)
2. 누적도수분포표 만들기 (각각의 값 이하의 요소가 모두 몇개 있는지 확인)
3. 목표 배열 만들기
4. 배열 복사하기

3. 구현 하기

class CountingSort {
  static void countingSort(int[] arr, int n, int max) {
    int[] f = new int[max + 1]; // 누적 도수
    int[] b = new int[n]; // 작업용 목표 배열
    
    for(int i = 0; i < n; i++) f[arr[i]]++; // 1단계: 도수분포표 만들기
    for(int i = 1; i <= max; i++) f[i] += f[i - 1]; // 2단계: 누적도수분포표 만들기
    for(int i = n - 1; i >= 0; i--) b[--f[arr[i]]] = arr[i]; // 3단계: 목표 배열 만들기
    for(int i = 0; i < n; i++) arr[i] = b[i]; // 4단계: 배열 복사
  }
  
  static int getMax(int[] arr) {
    int max = arr[0];
    
    for(int i = 1; i < arr.length - 1; i++) {
      if(arr[i] > max) max = arr[i];
    }
    return max;
  }
  
  public static void main(String[] args) {
    int[] arr = { 5,3,4,1,8,3 };
    int max = getMax(arr);
    countingSort(arr, arr.length, max);
  }
}

 

참고 자료

• 계수 정렬(Counting Sort) [ 실전 알고리즘 강좌(Algorithm Programming Tutorial) #12 ]