자료구조 :: 계수정렬 Counting sort (c/c++ 구현)

계수정렬 Counting sort

계수정렬은 다른 정렬에 비해 매우 빠른속도로 정렬할 수 있다. 

 

크기를 갯수로 세어보자

 

원소의 크기 범위만큼 배열을 만든다.

 

크기가 한정되어 있는 데이터 집단에서 사용하기 좋다.

(크기만큼 배열공간을 만들어야 하므로)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

위와 같이 1의개수는 3개,

2의 개수는 2개

3의 개수는 3개

4의 개수는 4개

5의 개수는 2개

각각의 값들이 몇개 인지 알았으니

그 개수만큼 출력해주면 된다.

1 1 1 2 2 3 3 3 4 4 4 5 5

 

#include <stdio.h>

int main(void){
    
    int count[5] = {0,0,0,0,0};
    int data[20] = {
        1,4,2,5,3,
        2,3,4,5,2,
        2,2,3,4,1,
        4,2,5,5,1
    };
    
    // 반복문 한번으로 정렬 완료 
    for(int i=0; i<20; i++){
        count[data[i]-1]++;
    }
    
    // 결과 출력 
    for(int i=0; i<5; i++){
        if(count[i] != 0){
            // 0일때는 출력 안해도 되니깐
            for(int j=0; j<count[i]; j++) {
                printf("%d ", i+1);
            }
        }
    }
    
    return 0;
}​

 

 

단점이라고 한다면, 데이터의 수가 매우 클경우

메모리 공간이 많이 필요하다는 점이다.

 

계수 정렬의 시간복잡도는 O(N)으로 매우 빠르다.

 

관련 글

2018/04/29 - [Algorithm] - 자료구조 :: 힙 정렬 Heap sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 퀵 정렬 Quick sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 삽입정렬 Insertion sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 버블정렬 Bubble sort (c/c++ 구현)

2018/04/28 - [Algorithm] - 자료구조 :: 선택정렬 Selection sort (c/c++ 구현)