[자료구조] counting sort 계수정렬

안녕하세요 주인장 H입니다. 

지금까지 선택, 버블, 삽입, 퀵, 병합, 힙 정렬의 개념을 공부해보았고, 

가장 빼운 정렬은 O(N * log N)이 나오는 퀵, 병합, 힙 정렬 이였습니다. 

하지만 이보다 더욱 빠른 정렬을 진행해야 한다면 어떻게 해야할까요 

 

다음의 3 이하의 데이터 자연수들을 오름차순으로 정리하세요 

1 3 2 3 1 2 3 2 1 3

 

10개의 데이터가 모두 3안에 있는걸 알 수 있는데요. 이처럼 범위조건이 있는 경우에 한해 

굉장히 빠른 알고리즘 입니다. 속도는 O(N)입니다. 

 

계수정렬은 크기를 기준으로 갯수를 세면 어떨까? 란 발상에서 시작합니다.

 

즉 세개의 배열을 만들고 1이면 arr[0]++ 3이면 arr[2]++ 이런식으로 숫자를 세주면 됩니다. 

그러면 숫자의 갯수가 세질테고 

1을 arr[0]의 값만큼, 2를 arr[1]의 값만큼 반복해서 출력해주면 되겠지요. 

 

//범위조건이 있는 경우에 한해서 빠른 정렬 
//크기를 기준으로 갯수를 세면 어떨까? 
//위치 바꿀 필요 없음 O(N)

#include <stdio.h>

int main(void) {
	int temp;
	int count[5];
	int array[30] = { 1,3,2,4,3,2,5,3,1,2,
					1,3,2,4,3,2,5,3,1,2,
					1,3,2,4,3,2,5,3,1,2 };
	//count 0으로 초기화 
	for (int i = 0; i < sizeof(count) / sizeof(int); i++) {
		count[i] = 0;
	}
	//count 에 array index안에 있는 값에 맞게 알맞은 count index 에 넣어줌 
	for (int i = 0; i < sizeof(array) / sizeof(int); i++) {
		count[array[i] - 1]++;
	}
	//count[i]에 있는 값을 값만번 출력한다. 
	for (int i = 0; i < sizeof(count) / sizeof(int); i++) {
		if (count[i] != 0) {
			for (int j = 0; j < count[i]; j++) {
				printf("%d ", i + 1);
			}
		}
	}
	return 0;
}