03. 계수 정렬

계수 정렬의 정의

• Counting Sort는 크기를 기준으로 데이터의 개수를 세는 정렬 알고리즘
• 각 데이터를 바로 크기 기준으로 분류함
  --> O(N)의 시간 복잡도

계수 정렬의 과정

계수 정렬에서는 숫자 자체가 인덱스가 됨

계수 정렬의 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define MAX_VALUE 10001
// 계수정렬은 해당 숫자 자체를 인덱스로 삼기에 최대값이 꼭 정의되어야 함
// 그만큼 메모리를 많이 사용하는 대신 빠르게 정렬
// 최대값을 넘어가는 숫자는 정렬 불가

int n, m;
int a[MAX_VALUE];

// main 함수
int main(void) {
	int n;
	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");
	return 0;
}

계수정렬은 데이터의 크기가 한정적일 때 사용