2-4) [C] 계수 정렬(Counting Sort)

1) 계수 정렬이란?

반드시 어떠한 범위안에 존재하는 데이터들로 이루어진 데이터 배열에 한하여 데이터의 크기를 기준으로 카운트하여 정렬하는 알고리즘이다.

 

2) 계수 정렬의 시간복잡도

크기를 기준으로 개수를 세어주기 때문에 위치를 바꿀 필요가 없다. 따라서  O(n)이다. 

 

3) 계수 정렬 구현

#include <stdio.h>

int main() {
	int A[10] = { 1, 4, 5, 2, 2, 4, 1, 3, 5, 3 };
	int count[5];//빈도수 측정결과를 담을 배열
	
	for (int i = 0; i < 5; i++) {
		count[i] = 0;
	}

	for (int i = 0; i < 10; i++) {
		count[A[i]]++;
	}

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

결과화면

1 1 2 2 3 3 4 4 5 5