정렬알고리즘_계수정렬 [7/8]

[ 계수 정렬이란? ]

• 데이터의 크기를 기준으로 정렬하는 방식
• 데이터의 정렬 범위가 정해져있을 때 O(N)의 시간 복잡도를 가지므로 매우 빠름
• 다른 방식들은 숫자 외에도 적용할 수 있지만 계수 정렬은 숫자만 가능
• 숫자의 범위가 크고 분포가 넓을 경우(숫자 사이 간격이 클 경우), 메모리 비효율 발생

---

 

기본적인 방식은 매우 좋습니다만.. 숫자 범위가 엄청 넓은데 띄엄띄엄 숫자가 존재할 경우에는 메모리 공간 낭비가 심하고 비효율적이 될 수 있습니다. 예를 들어 이 방식에서는 1 ~ 10000 까지의 숫자가 있을 때 temp[10000]의 임시 공간을 만들어줘야 한다는 단점이 있습니다. 중간에 빈 공간이 많이 발생할 수도 있구요. 해쉬방식으로 배열을 나누고 연결리스트 구조를 사용해도 되겠다는 생각은 들지만.. 그럴바에는 그냥 퀵,힙,병합정렬이 더 효율적으로 보입니다.

 

#include <stdio.h>

void main()
{
	int arr[] = { 1,1,3,5,1,5,4,6,2,1,3,8,2,3,4,8,3,5,7,4,6,3,2,1,9,4,0 };
	int size = sizeof(arr) / sizeof(int);

	/* 배열 출력 */
	printf("\n 정렬 전 : ");
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);

	/* 정렬 */
	int temp[10] = { 0 };	
	for (int i = 0; i < size; i++)	// 숫자 카운트
		temp[arr[i]]++;
	
	int w = 0;	// 원본에 재 정렬
	for (int i = 0; i < 10; i++)
		for (int j = 0; j < temp[i]; j++)
			arr[w++] = i;

	/* 배열 출력 */
	printf("\n 정렬 후 : ");
	for (int i = 0; i < size; i++)
		printf("%d ", arr[i]);

	printf("\n");
}