계수 정렬(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");
}