[ 정렬 ] 카운팅 정렬(Counting Sort) (C++)

이번 글에서는 카운팅정렬(Counting Sort) 에 대해서 다뤄보고자 한다.

사실 카운팅정렬은 값을 비교해서 정렬하는 방식이라기 보다는 값의 갯수를 세고 그 갯수에 따라서 위치를 설정해주는 방식이다.

즉, 데이터들간의 크기를 비교하거나 그런 정렬 방식이 아니다.

동작 원리는 다음과 같다.

와 같은 배열이 있다.

1. 각 데이터의 갯수를 모두 Count 해준다.

   - 위의 경우 Count[3] = 2; Count[2] = 1; Count[1] = 2가 될 것이다.

2. 누적합 계산하는 방식으로 1부터 최댓값까지 계산을 해준다.

   - 누적합을 계산한다는 것은 갯수를 누적하면서 더해준다는 것이다.

     즉 위의 경우 Count[1] = Count[1] + Count[0] = 2;

     Count[2] = Count[2] + Count[1] = 1 + 2 = 3

     Count[3] = Count[3] + Count[2] = 2 + 3 = 5

3. 새로운 배열에 누적합의 갯수를 --해준 후에 저장해준다.

   - 쉽게 얘기하자면 우리는 2번 과정에 의해서 Count[1] = 2 , Count[2] = 3, Count[3] = 5 라는 것을 알아냈다.

     즉, 이 누적합이 의미하는 것은 들어갈 수 있는 최대 위치를 의미한다.

     Count[1] = 2라고 되어있다. 즉, 정렬하게 되면 '1'이라는 값이 들어갈 수 있는 최대 위치는 두번째라는 것이다.

     여기서 문제점 ! 최대 위치가 두 번째라는 것은 Index번호 몇번을 의미할까?? 바로 '1'을 의미한다.

     왜냐하면 배열은 0부터 존재하기 때문이다.

     따라서 우리는 값을 -- 해준 후 새로운 배열에 넣어주면 된다. 즉 위의 배열을 처음부터 탐색을 하게 되면 가장 첫 값은 '3'이기

     때문에 Count[3]을 -- 해준 후, 새로운 배열에 넣어준다. 그림으로 이해해보자.

여기서 가장 첫 값이 '3'이 나왔다.

현재 Count[3] = 5 이다. Count[3]을 Index번호에 알맞게 맞춰주기 위해서 --를 해주면 Count[3] = 4.

즉, 새로운 배열의 '4'번 Index가 '3'이 된다는 것이다.

그 다음 2를 해보자. 현재 Count[2] = 3 이다.

이 3이라는 값을 Index를 맞춰주기 위해서 --를 해주면 Count[2] = 2가 된다.

즉, 새로운 배열에 '2'번 Index가 2가 된다는 것이다.

그 다음 3을 해보자. 현재 Count[3] = 4 이다.

--를 해주게 되면 Count[3] = 3. 즉, 새로운 배열에 '3'번 Index값이 3이 된다는 것이다.

나머지 1도 위와 같은 방식으로 하게 되면 결과적으로 정렬된 형태의 배열을 볼 수 있다.

# 시간복잡도

- 위의 과정을 봐서 알겠지만 비교가 필요하지도 않다. N번 탐색하면서 갯수 Count해주기, 누적합 구하기, 새로운 배열에 다시

  값을 넣어주기 과정이 끝이다.

  즉, 시간복잡도로 나타내면 O(N) 번 정도의 시간복잡도를 갖는다.

  하지만, 데이터가 작을 때는 정말 빠르지만 데이터가 많아질수록 속도가 많이 늦어진다고 한다. 또한, 추가적으로 메모리가 요구

  되는 정렬 방식이다.

  그리고 본인은 마지막에 새로운 배열에 값을 넣어줄 때 원본 배열의 가장 처음(0번 Index)부터 값을 넣어줬지만 이렇게 할 경우

  Unstable한 정렬이다. 반대로 가장 마지막 값 부터 넣어준다면 Stable한 정렬로 구현 가능하다.

  여기서 Unstable하다, Stable하다라는 것은, 동일한 데이터에 대해서 그 순서가 바뀌지 않는 것이다.

  위의 그림에서 한 부분을 따오면....

   이 그림에서 '3' 2개를 봐보자. 원본 맵에서 0번 Index에 '3'이 하나 있고, 2번 Index에 '3'이 하나 있다.

   하지만 정렬하고 난 후에 보면, 더 앞에 있던 즉, 0번 Index에 있던 '3'이 2번 Index에 있던 '3'보다 더 뒤로 가게 되었다.

   이러한 정렬을 Unstable하다고 표현한다. 보통 우리가 주로 하는 정렬에서 이 부분까지 고려하지는 않지만 이런것도 있다 라는

   것을 알고 있자 !

[ 소스코드 ]

#include<iostream>
#include<cstdlib>
#include<ctime>
 
#define MAX 100
using namespace std;
 
int Arr[MAX];
int N_Arr[MAX];
int Max_Value;
int Count[101];
bool Flag[101];
 
void Print(int A[])
{
    cout << "####################################################################################################################" << endl;
    int Cnt = 0;
    for (int i = 0; i < MAX; i++)
    {
        printf("%3d ", A[i]);
        Cnt++;
        if (Cnt == 20)
        {
            Cnt = 0;
            cout << endl;
        }
    }
    cout << "####################################################################################################################" << endl;
    cout << endl;
}
 
void Counting_Sort()
{
    for (int i = 0; i < MAX; i++) Count[Arr[i]]++;
    for (int i = 1; i <= Max_Value; i++) Count[i] = Count[i] + Count[i - 1];
    for (int i = 0; i < MAX; i++)
    {
        Count[Arr[i]]--;
        N_Arr[Count[Arr[i]]] = Arr[i];
    }
}
 
int main(void)
{
    srand((unsigned)time(NULL));
    for (int i = 0; i < MAX; i++)
    {
        Arr[i] = (rand() % 150) + 1;
        if (Max_Value < Arr[i]) Max_Value = Arr[i];        
    }
 
    cout << "[ Initialize Array State ] " << endl;
    Print(Arr);
    Counting_Sort();
    cout << "[ After Sort Array State ] " << endl;
    Print(N_Arr);
 
    return 0;
}