Counting Sort ( 계수 정렬 )

계수 정렬은 삽입, 버블, 선택, 퀵, 합병 정렬들과 같이 비교를 수행하는 방식이 아닌 비교를 하지 않는 Non-Comparisions Sorting Algorithm입니다.

그러면 여기서, 값을 정렬하는데 어떻게 비교 없이 수행하나요? 와 같은 질문이 있을 텐데요. 계수 정렬은 비교 대신 정렬할 수의 개수와 배열의 인덱스를 가지고 정렬을 수행하게 됩니다.



기본적인 흐름


2 1 2 4 5 3 6 5 3  을 정렬하고자 한다면

1의 개수는 1개,
2의 개수는 2개,
3의 개수는 2개,
4의 개수는 1개,
5의 개수는 2개,
6의 개수는 1개
이기 때문에 작은 수 부터 개수만큼 차례대로 나열하게 되면

1 2 2 3 3 4 5 5 6

으로 정렬이 되게 됩니다.


정렬 과정


  • 정렬할 배열 A, 추가 배열 C를 생성해준다.

  • 배열 C는 모든 값을 0으로 초기화해준다.

  • 배열 A의 값을 토대로 배열 C의 인덱스값을 참조하여 값을 1씩올려준다. (예를 들어 배열 A의 값중 3이 있다고 한다면, C의 3번째 인덱스 값을 1더해준다.)

  • 배열 c의 각 값들을 직전 값을 더해 업데이트 해준다.
    (예를 들어, 배열 C가 1,0,2,2 였다면, 1,1,3,5로 업데이트 해준다.)

  • 배열 C는 배열 A의 값들의 인덱스 값이므로, 배열 A를 끝에서부터 역순으로 훑으면서 배열 B에 정렬해 준다. (이때, 한 값을 B에 옮겨주었다면, 해당하는 인덱스의 배열 C의 값은 1을 빼준다.)


여기서 배열 A의 뒤의 값부터 역순으로 훑으면서 정렬하는 이유는 counting sort 는 stable한 특성을 갖고있는 정렬인데, 앞에서부터 정렬을 하게 되면 stable한 특성이 깨지기 때문이다.


예를들어, 아래와 같은 배열 A가 있다면, 원래 방법대로 뒤에서부터 훑게 되면 아래와 같이 정렬이 된다.

   A = { 3 5(a) 1 4 5(b) 2 }
   C = { 1 2 3 4 6 } 이 되어,

   A = { 1 2 3 4 5(a) 5(b) }


반대로 똑같은 A를 앞에서 부터 훑게 되면 아래와 같이 나오게 되면서 stable한 특성이 깨지게 된다.

    1 2 3 4 5(b) 5(a)

따라서 뒤에서 부터 훑으며 정렬을 하게 된다.



c++ 구현 코드


#include <iostream>
#include <cstdlib>  //time
#include <ctime>    //rand, srand
#include <string.h> //memset
#include <time.h>   //시간 측정

using namespace std;

#define MAX_ARRAY_SIZE 64   //정렬할 배열 숫자 개수

int maxValue=0;     //가장 큰 값

clock_t start, finish, used_time=0;    //실행 시간 측정을 위한 변수

//배열의 item을 random으로 삽입
void input_random(int *array,int arrlen){
    srand((unsigned int)time(NULL));
    for(int i=0;i<arrlen;i++){
        array[i]=rand()%MAX_ARRAY_SIZE + 1;
        maxValue = (maxValue < array[i]) ? array[i] : maxValue;     //가장 큰 값 찾기
    }
}

void display(int *array,int arrlen){
    for(int i=0; i<arrlen;i++){
        cout.width(3);
        cout << i+1 <<". ";
        cout.width(2);
        cout << array[i] << endl;
    }
}

//실행 시간을 측정 및 출력하는 함수
void CalcTime(void){
    used_time=finish-start;
    printf("\n*********** result **********\n     time : %lf sec\n", (double)(used_time)/CLOCKS_PER_SEC);
}

int* count_sort(int *array,int arrlen){
    int *c = new int[maxValue+1];
    int c_size = maxValue+1;
    int *b = new int[arrlen];

    memset(c,0,c_size*sizeof(int)); //배열c 0으로 초기화

    /*각 숫자 횟수 카운틱하며 c배열 인덱스 값 증가*/
    for(int i = 0; i < arrlen ; i++){
        c[array[i]]++;
    }

    /*배열 c의 인덱스 값 누적합 구하기*/
    for(int i=1; i < c_size; i++){
        c[i] += c[i-1];
    }

    /*배열 A역순으로 훑으며, 배열 C참조하여 정렬*/
    for(int i = arrlen-1; i >= 0; i-- ){
        b[c[array[i]]-1] = array[i];
        --c[array[i]];
    }
    return b;
}

int main(){
    int *array = new int[MAX_ARRAY_SIZE];

    input_random(array,MAX_ARRAY_SIZE);     //배열에 랜덤값 삽입
    delete array;

    start = clock();
    array = count_sort(array,MAX_ARRAY_SIZE);       //계수 정렬
    finish = clock();
    display(array,MAX_ARRAY_SIZE);          //show array
    CalcTime();

    delete array;
    return 0;
}



특징


시간 복잡도는 O(n+k)O(n) 또는 O(k) 를 갖습니다.
( 여기서 n은 input의 개수, k는 input으로 들어온 n의 범위 == 추가 배열 c의 범위 )

그 이유는 n이 k보다 클 수도 있고 k가 n보다 클 수 있기 때문입니다.


예를 들어

1,1,1,1,1,1,1,1 과같이 1이 10개로 n이 10이 들어왔다면, 이때 k는 2가 되고,
1 500 의 input이 주어진다면 n은 2에 불과하지만, k는 501이 되게 됩니다.

범위가 넓어지게 되면 추가 메모리 공간이 많이 필요해지고, 또 범위를 계산해서 가장 큰 수가 무엇인지 판별하는 추가 로직도 도는 등 추가 작업이 필요하게 됩니다.


따라서, 점수알파벳같은 좁은 범위의 데이터를 정렬할 때 유용합니다.

stable 한 정렬 방법으로 radix sort 시 사용되는 정렬입니다.