9. 계수 정렬 - 계수정렬의 원리 / 구현하기

계수정렬

계수정렬(Counting Sort)는 크기를 기준으로 데이터의 개수를 세는 정렬 알고리즘이다. 각 데이터를 크기를 기준으로 바로 분류하므로, O(N)의 시간 복잡도를 가진다.

퀵 정렬이나 다른 정렬 알고리즘에 비해서 많은 메모리(값의 크기만큼 인덱스를 모두 가져야하므로)를 요구하는 한편, 빠르게 동작한다. 상당히 많은 메모리 소모가 있기 때문에 크기 제한(정렬하고자하는 Data가 가질 수 있는 가장 큰 값에 대한)이 존재해야 한다.

 

계수정렬 구현하기

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX_VALUE 10001 //정렬할 data가 가질 수 있는 가장 큰 값

int n, m;
int a[MAX_VALUE];

int main(){
    scanf("%d", &n); //입력받을 값의 갯수
    for(int i= 0; i < n; i++) { //정렬
        scanf("%d", &m); //값이 입력될 때마다
        a[m]++; // 그 값에 해당하는 Index의 원소를 1씩 증가
    }
    for(int i=0; i < n; i++){
        while (a[i] != 0){
            printf("%d", i);
            a[i]--;
        }
    }
}

 

요약

1. 계수정렬은 시간복잡도가 O(N)인 정렬 알고리즘이다.
2. 계수 정렬은 데이터의 크기가 한정적일 때 사용할 수 있다.