카운팅 정렬 (Counting Sort)

1. 개념 👑

  '계수 정렬'이라고도 불리는 '카운팅 정렬(Counting Sort)'은 각 원소들이 몇 개씩 있는지 나타내는 count배열을 활용하는 정렬 알고리즘이다.

  각 원소의 값이 count 배열의 인덱스가 되므로 '정수나 정수로 표현할 수 있는 자료'에 대해서만 적용 가능하다.

 

2. 동작방식 🎓

  동작 방식은 다음과 같다.

1. 원소의 최댓값을 포함할 수 있는 배열 설정
2. 각각의 원소가 몇 번 등장하는지 카운팅
   count 배열의 인덱스 = 원소 값
   count 배열의 값 = 등장 횟수
3. count 배열을 누적합으로 만들어주기
4. 정렬되지 않은 배열(초기값)의 뒤에서부터 돌면서, 원소의 값과 동일한 인덱스가 가리키는 곳에 원소 배치해 주기

  '0 2 1 1 4 4 4 3 5'가 주어졌을 때 동작방식을 아래의 그림을 통하여 이해해 보자.

  동작방식에서 2가지 의문점이 생길 수 있다.

1. 배열의 뒤에서부터 돌면서 자리를 배치할 때 count값을 감소시키는 이유는?
     count값을 감소시켜야지 다음에 같은 값이 들어왔을 때 알맞은 자리에 찾아갈 수 있다. 위에서 count[4]에 해당하는 값을 계속해서 감소시켰기 때문에 '7, 6, 5'의 인덱스에 해당하는 위치에 4가 배치될 수 있었다.
2. 누적합을 해줘야 하는 이유는?
     누적합을 하지 않는 경우에는 count 배열을 돌면서 'idx값을 idx에 해당하는 값'만큼 배치하면 된다. 위의 예제에서는 '0을 1번, 1을 2번, 2를 1번, 3을 1번, 4를 3번, 5를 1번' 배치하면, '0 1 1 2 3 4 4 4 5'를 얻을 수 있다.
     하지만, 위의 경우와 달리 연속된 값이 아닌 '1 2023 0'을 정렬하는 과정을 생각해 보자. 이런 경우 0부터 2023까지 count를 돌아야 한다.
     그러나 누적합을 사용하면 위에서 동작했던 것처럼 원소의 개수인 N만큼만 count에 접근하면 된다. 이러한 점으로 인해 count를 누적합해서 사용한다.

 

3. 구현(JAVA) 🎩

public static void main(String[] args) {
    int arr[] = {0, 2, 1, 1, 4, 4, 4, 3, 5};
    int sorted_arr[] = new int[arr.length];

    int maxValue = 0;
    for(int i : arr) {
        maxValue = Math.max(maxValue, i);
    }
    // 1. 원소의 최댓값을 포함할 수 있는 배열 설정
    int count[] = new int[maxValue + 1];

    // 2. 각각의 원소가 몇 번 등장하는지 카운팅
    for(int i = 0; i < arr.length; i++) {
        count[arr[i]]++;
    }

    // 3. count 배열을 누적합으로 만들기
    for(int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    // 4. 뒤에서부터 배열을 돌면서 원소의 값과 동일한 인덱스가 가르키는 곳에 원소 배치해주기
    for(int i = arr.length - 1; i >= 0; i--) {
        count[arr[i]]--;
        sorted_arr[count[arr[i]]] = arr[i];
    }

    for(int i : sorted_arr) {
        System.out.print(i + " ");
    }
    // 0 1 1 2 3 4 4 4 5 
}

 

4. 시간복잡도 & 공간복잡도 👒

시간복잡도

  원소의 개수를 N이라 하고 원소의 최댓값을 K라고 하자. 동작과정에서의 시간복잡도는 아래와 같다.

• counting 배열을 만들기 → O(N)
• counting 배열을 누적합 시키기 → O(N + K)
• 뒤에서부터 배열을 돌면서, 해당하는 값을 이용하여 인덱스에 원소 넣어주기 → O(N)

  그러므로 시간복잡도는 O(N + K)이다. 하지만 일반적으로는 K가 큰 값을 가지지 않으므로 평균적인 시간복잡도는 O(N)이다.

	최선(BEST)	평균(AVERAGE)	최악(WORST)
시간복잡도	O(N)	O(N)	O(N + K)

공간복잡도

  K만큼 배열을 만들어줘야 하므로 공간복잡도는 O(K)이다.

 

5. 장점 & 단점 🧢

장점

• 시간복잡도(평균)가 O(N)이다. (일반적인 상황에서 가장 빠른 정렬 알고리즘인 퀵 정렬의 시간복잡도 O(N logN)에 비하면 매우 빠른 것이다.)

단점

• 추가적인 메모리 공간이 필요하다.
• 일부 값(최댓값)에 의해 메모리의 낭비가 심해질 수 있다.

 

해당 글은
Gyoogle 님의 '계수 정렬(Counting Sort)',
멍멍멍 님의 'Counting Sort : 계수 정렬',
Chappi 님의 '알고리즘 6일차 - O(n) 정렬, 계수 정렬'
을 참고하였습니다.