12. 계수 정렬(Counting Sort)

속도가 O(N * log N)이 나오는 퀵 정렬, 병합 정렬, 힙 정렬보다 빠르게 정렬하는 방법.

단 범위조건이 있어야 한다.

시간복잡도는 O(N)으로 매우 빠르다.

크기를 기준으로 갯수를 센 후 그 수 만큼 출력하면 된다.

크기가 한정되어 있는 배열만이 계수정렬을 사용할 수 있다는 특징이 있다.

#include <stdio.h>
 
int main(void)
{
    int temp;
    int count[6];
    int array[30] = {1, 3, 2, 4, 3, 2, 5, 3, 1, 2,
					 3, 4, 4, 3, 5, 1, 2, 3, 5, 2,
					 3, 1, 4, 3, 5, 1, 2, 1, 1, 1};
    for(int i = 1; i <= 5; i++)
    {
    	//인덱스의 모든 값을 0으로 설정
        count[i] = 0;
    }
    for(int i = 0; i < 30; i++)
    {	
    	//해당 숫자 칸에 1 증가
        count[array[i]]++;
    }
    for(int i = 1; i <= 5; i++)
    {
    	//배열 값이 0이 아닌 이상 출력
        if(count[i] != 0)
        {
            for(int j = 0; j < count[i]; j++)
                printf("%d ", i);
        }
    }
    return 0;
}

 

 

출력 결과