[알고리즘] 계수 정렬(Counting Sort)

이번시간에는 계수 정렬에 대해 공부해보겠습니다.

 

계수 정렬의 시간 복잡도는 O(n)입니다. n번만에 숫자를 정렬할 수 있습니다 ! 다른 빠르다는 정렬 알고리즘도 O(nlongn)시간을 가지는데 계수 정렬은 어떻게 O(n)시간을 가질까요 ? 

 

먼저 다음의 숫자를 계수정렬을 사용하여 정렬해 보겠습니다. 계수정렬은 각 숫자의 빈도수를 체크하여 정렬합니다.

 

5 0 0 2 3 1 1 3 4

배열에 숫자의 빈도수가 체크되어있고 [2,2,1,2,1,1,] 그대로 출력하면 0 0 1 1 2 3 3 4 5가 됩니다. 하지만 계수정렬에는 몇가지 문제점이 있습니다.

 

1. 정렬 대상이 단순 정수가 아니라면 ? 

만약 { 이름, 주소, 나이 } 정보를 가진 사람을 나이순으로 정렬해야 한다면? 위의 방법이라면 '나이'순으로는 정렬할 수 있습니다. 하지만 { 이름, 주소, 나이 }가 같이 움직여야 의미가 있는데 '나이'만 정렬하면 의미가 없을 것입니다.

 

2. 숫자사이의 차이가 많이 난다면 ?

극단적으로 0,5 100, 1000000를 정렬하는 경우 6 ~ 999999사이의 공간은 그저 빈 공간으로만 존재할 것입니다. 메모리낭비가 되겠죠.

 

이런 이유때문에 위의 방법처럼 단순히 출력하는 방법이 아닌 다른 방법을 사용합니다.

 

단순히 숫자가 등장하는 횟수가 아닌, 횟수를 누적합으로 계산합니다.

원래 각 숫자의 횟수는 [2,2,1,2,1,1,] 였습니다. 누적합으로 계산하면 위의 결과처럼 나오게 되는데, 누적합으로 계산한다는 것은 무엇을 의미할까요 ?

 

바로 해당 숫자의 위치를 나타내게 됩니다.

 

0의 횟수가 2라는 말은, 0보다 작은 숫자가 없으니 처음 1,2위치에 존재합니다. 그리고 1의 횟수가 4라는 의미는 2 < 위치 <= 4를 의미합니다. 0이 1,2 위치를 차지하고 있기 때문에 1이 차지할 수 있는 위치는 3,4가 되겠죠. 마찬가지고 2의 위치는 4 < 위치 <= 5이며, 1이 3,4를 차지하고 있기 때문에 5에 위치하게 됩니다.

 

그리고 여기서 중요한 점은, 각 숫자의 위치가 정해졌을 때는 해당 숫자의 위치-1을 해주어여 합니다. 한번 사용했기 때문이죠.

#include <iostream>

using namespace std;

int main(){

    int arr[9] = {5,4,3,3,2,1,1,0,0};
    int check[6]={0};
    int result[9];

    for(int i=0;i<9;i++){
        check[arr[i]]++;                 // 빈도수 체크
    }

    for(int i=1;i<6;i++){
        check[i] = check[i]+check[i-1]; // 빈도수 누적합 계산
    }

    for(int i=8;i>=0;i--){         
        result[check[arr[i]]] = arr[i];  // result[]의 check[arr[i]] 값을 index로하는 곳에 arr[i] 값을 대입
        check[arr[i]]--;                 // arr[i] 값을 하나 사용했기 때문에 다음 위치는 현재 arr[i]위치의 -1
    }

    for(int i=1;i<=9;i++){
        cout << result[i] << " ";       
    }

    return 0;
}

눈여겨 볼 점은 result[check[arr[i]]] = arr[i]입니다. 위에서 check[]에는 arr[i]값을 누적값, 즉 arr[i]를 사용했을 때의 그 값이 들어갈 위치(index)가 들어가 있습니다. 그렇기 때문에 result[check[arr[i]]] = arr[i]라는 의미는 arr[i]를 선택했을 때 적절한 result[]의 적절한 위치에 arr[i]를 대입하라는 의미입니다. 또 arr[i]값을 하나 사용했기 때문에 arr[i]의 위치를 관리하는 check[arr[i]]값을 -1해주게 되는 것이죠.