[Week1] 계수 정렬 (Counting Sort)

Comparison Sort

N개 원소의 배열이 있을 때, 이를 모두 정렬하는 가짓수는 N!임

따라서, Comparison Sort를 통해 생기는 트리의 말단 노드가 N! 이상의 노드 갯수를 갖기 위해서는,
2^h >= N! 를 만족하는 h를 가져야 하고, 이 식을 h > O(nlgn)을 가져야 한다.
(h는 트리의 높이,,, 즉 Comparison sort의 시간 복잡도임)

 

이런 O(nlgn)을 줄일 수 있는 방법은 Comparison을 하지 않는 것

 

정렬하는 숫자가 특정 범위 안에 있을 때 사용함

 

Process

public static void countingSort(int[] arr, int n) {
    // {5, 4, 3, 2, 1}

    int[] buffer = new int[n];
    int m = getMax(arr, n);
    int[] count = new int[m + 1];
    // 최댓값이 담길 수 있도록 사이즈 잡기

    // count 배열의 값을 증가시켜주기
    for (int i = 0; i < arr.length; i++) {
        count[arr[i]]++;
    }
    // count == {0, 1, 1, 1, 1, 1}

    // 누적합 구해주기
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }
    // count == {0, 1, 2, 3, 4, 5}

    for (int i = arr.length - 1; i >= 0; i--) {
        count[arr[i]]--;
        buffer[count[arr[i]]] = arr[i];
    }
}

 

시간복잡도

O(n + k) : k는 배열에서 등장하는 최댓값

공간복잡도

O(k) : k 만큼의 배열을 만들어야 함. 

 

장점

O(n)의 시간복잡도

 

단점

배열 사이즈 N만큼 돌 때, 증가시켜주는 Count배열의 크기가 크다.