📒 갈무리 - 계수정렬(Counting Sort)

📌 계수정렬이란?

- 양의 정수들의 개수를 Counting하며 정렬하는 것

- 정수 정렬 알고리즘중의 하나이다.

- 계수 정렬은 비교 정렬이 아니다.

 

📌 계수정렬 진행 순서

1. 개수를 Counting할 배열을 만든다.

2. 정렬할 데이터를 순회하며 해당 데이터의 index를(위에서 만든 배열의 index) 하나씩 증가 시킨다.

 

📌 직접 구현해 보자...

// C#
        // 10이하의 데이터들을 정렬하는 Counting Sort.
        public void CountingSort(int[] data)
        {
            int[] counting = new int[10];
            for (int i = 0; i < data.Length; i++)
            {
                counting[data[i]]++;
            }

            // 데이터 정렬하며 출력.
            for (int i = 0; i < counting.Length; i++)
            {
                for (int j = 0; j < counting[i]; j++)
                {
                    Console.Write(i + ", ");
                }
            }
        }

 

📌 계수정렬의 특징

- 해당 양의 정수의 개수를 index에 Conuting하며 정렬한다.

- O(N)의 시간 복잡도를 갖는다.

- 정렬의 기준이 크기일 때 빠르게 정렬 시킬 수 있다.

- 정렬할 데이터의 가장 큰 값을 Counting배열의 크기로 설정해야 한다.