계수 정렬

계수 정렬(Counting Sort)

- 크기를 기준으로 데이터의 개수를 세는 정렬 알고리즘

- 각 데이터를 바로 크기를 기준으로 분류하므로 0(N)의 시간 복잡도를 가짐 

 

인덱스 : 0 1 2 3

원소 : 2 3 3 2

차례대로 원소의 개수만큼 출력 : 0011122233

 

#define _CRT_SECURE_NP_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#define MAX_VALUE 10001

// 정렬 전: 1, 5, 39, 8, 4, 888888
// 정렬 후: 1, 4, 5, 8, 39
int n, m;
int a[MAX_VALUE];

int main(void) {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) { scanf("%d", &m); a[m]++; }
    for (int i = 0; i < MAX_VALUE; i++) {
        while (a[i] != 0) { printf("%d ", i); a[i]--; }
    }
    system("pause");
}