[알고리즘]카운팅 정렬 (Counting Sort) 알고리즘

 

카운팅 정렬 알고리즘은 최댓값과 입력 배열의 원소 값 개수를 누적합으로 구성한 배열로 정렬을 하는 알고리즘이다.

---

작동 방식을 아래에 두가지 예제에서 확인해보자

 

이해하기 간략한 예제 (대신 누적합 부분과 인덱싱 부분이 빠져있음)

 

 

Counting Sort Visualization

위에 카운팅 정렬 사이트를 가서 Couting Sort 버튼을 클릭하면 보이는 방법이 더 정확한 정렬 방법을 확인할수가 있다.

 

1. 중복되는 무작위 값을 가진 입력 배열이 있다 (단 배열 최대값은 9까지만 존재)
2. 먼저 배열에 원소 값들의 갯수를 저장하는 배열 (카운팅 배열)을 생성한다.
3. 각 원소 값들의 갯수를 카운팅해서 카운팅 배열에 저장을 해준다.
4. 카운팅 배열에 각 요소들에 대해서 직전 요소들의 값을 더해준다. (누적합)
5. 입력 배열과 동일한 크기의 출력 배열을 다시 만들어주고 카운팅 배열에 역순으로 카운팅 배열의 값을 인덱스로 해당되는 값들을 저장해준다.

---

위에 예제를 C# 코드로 구현한 것이다.

int n = int.Parse(Console.ReadLine());
int[] nums = new int[n];

for(int i = 0; i < n; i++)
{
    nums[i] = int.Parse(Console.ReadLine());
}


// 카운팅 정렬 메소드
static void CountingSort(int[] arr)
{
    // 카운팅 배열 생성 
    int[] counting = new int[arr.Max() + 1];
    int[] result = new int[arr.Length];

    // 입력 배열값 각각 갯수만큼 카운팅 배열값에 카운트
    for(int i = 0; i < arr.Length; i++)
    {
        counting[arr[i]]++;
    }

    // 누적합을 진행
    for(int i = 1; i < counting.Length; i++)
    {
        counting[i] += counting[i - 1];
    }

    // arr[i]에 해당하는 값을 가지는 카운팅 배열을 1 감소시키고
    // 카운팅 배열의 값을 인덱스로 해서 Result 배열에 해당 arr[i] 값을 저장
    for(int i = arr.Length - 1; i >= 0; i--)
    {
        int value = arr[i];
        counting[value]--;
        result[counting[value]] = value;
    }

    Console.WriteLine(String.Join("\n", result));
}


CountingSort(nums);

---

카운팅 정렬 알고리즘의 특징은 주어진 배열의 값 범위가 작은 경우 빠른 속도를 가진 알고리즘이다.

카운팅 배열을 추가적으로 선언해줘야 되기 때문에 수의 범위가 너무 큰 경우에는 메모리 낭비가 심한 알고리즘이다.

---

시간복잡도는 O(n + K) 알고리즘이다.