7. 계수 정렬

계수 정렬

계수 정렬은 범위 조건이 있는 경우 엄청 빠른 알고리즘입니다. 이 알고리즘의 시간 복잡도는 O(n)으로 엄청 빠른 속도를 자랑합니다. 계수 정렬의 메인 아이디어는 단순하게 크기를 기준으로 갯수를 세는 것 입니다. 이 알고리즘은 위치를 바꾸거나 할 필요 없이 모든 데이터에 한 번씩만 접근해서 크기를 기준으로 갯수를 세주기만 하면 되기 때문에 매우 효율적입니다.

#include <stdio.h>

int main() {
	int temp;
	int count[5];
	int array[15] = {
		1, 3, 2, 4, 3, 2, 5, 3, 1, 2,
		3, 4, 4, 3, 5
	};

	for (int i = 0; i < 5; i++) {
		count[i] = 0;
	}
	
	for (int i = 0; i < 15; i++) {
		count[array[i] - 1]++; // 각 수에 맞는 인덱스의 값을 1씩 증가시킴
	}

	for (int i = 0; i < 5; i++) {
		if (count[i] != 0) {
			for (int j = 0; j < count[i]; j++) {
				printf("%d", i + 1);
			}
		}
	}
	
	return 0;
}