계수정렬(Counting Sort)

Goal

      - Counting Sort 에 대해 설명할 수 있다.

      - Counting Sort 과정에 대해 설명할 수 있다.

      - Counting Sort를 구현할 수 있다.

      - Counting Sort의 시간 복잡도를 계산 할 수 있다.

---

1. Counting Sort Summary

 

   - '범위 조건'이 있는 경우에 한해서 제일 빠른 알고리즘 O(N)

   - '크기의 기준으로' 세는 알고리즘

---

2. Counting Sort Processing

 

    - 원소의 크기 범위만큼 배열을 만든다

    - 각각 값들이 몇개인지 확인 후 그 개수만큼 출력

 

---

3. Counting Sort Coding

//계수정렬
#include <stdio.h>

int main(void)
{
	int i , j, temp;
	int count[5];
	int array[30] = {1, 3, 2, 4, 3, 2, 5, 3, 1, 2,
					 3, 4, 4, 3, 5, 1, 2, 3, 5, 2, 
					 3, 1, 4, 3, 5, 1, 2, 1, 1, 1};
	//count 배열에 있는 원소를 모두 0으로 만든다. 
	for( i = 0 ; i < 5; i++)
	{
		count[i] = 0;
	}
	//array 배열에 각각 인덱스를 count배열에 담기 
	for( i = 0 ; i < 30; i++)
	{
		count[array[i] - 1]++;
	}
	//정렬
	for(i = 0 ; i < 5; i++)
	{
		if(count[i] != 0)
		{
			for(j = 0; j < count[i]; j++)
			{
				printf("%d ", i + 1);
			}
		}
	  }  
	return 0;
 }

---

4. 계수 정렬 시간 복잡도

 

            - '범위 조건'이 있는 경우에 한해서 굉장히 빠른 알고리즘O(N)

            - 한정된 데이터 안에서는 빠르지만 정렬할 데이터 크기에 의존하는 알고리즘