계수 정렬 (Counting sort)

계수 정렬 이란 단순히 '크기 기준' 으로 세는 알고리즘이다.

범위가 한정되어있을때 가장 빠른 속도를 낸다.

시간 복잡도는 O(N) 이다. 

 

 

 

알고리즘

 

1. 사실 알고리즘 이라고 할것도 없다.

2. 그냥 배열에서 해당 숫자의 갯수를 센다음

3. 작은 값부터 갯수만큼 출력하면된다 .. 

 

 

코드

#include <stdio.h> 
 
 
int main(void) {
 
    int count[5] = { 0,0,0,0,0 };
    int data[20] = { 2,3,4,1,3,5,4,2,1,3,2,4,5,1,2,3,5,4,2,3 }; // 반복문 한번으로 정렬 완료 
    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;
}
 

 

 

 

 

모든 글의 내용은 나동빈님 블로그를 참고 하였습니다.

https://blog.naver.com/ndb796/221228342808