계수 정렬(CountingSort) 구현

O(n+k) (k는 데이터의 최댓값을 의미한다.)

카운팅 정렬은 가장 큰 데이터에 따라 효율이 좌지우지된다. 

쉽게 설명하자면 특정 데이터의 개수(1이 두 개 있다면 2)를 데이터의 값에 대응하는 위치에 저장한 뒤, 자신의 위치에서 앞에 있던 값을 모두 더한 배열을 만든 뒤, 거기서 데이터가 들어가야 할 위치를 찾아내는 정렬 알고리즘이다. 

이 경우에 데이터의 최댓값을 k라 두면, 시간 복잡도는 O(n+k).

n이 아무리 작아도 동작시간이 크다. 

그럴 땐 위의 정렬들을 사용하는 게 바람직하다. 반대로 k가 매우 작다면, 오히려 선형시간의 효과를 볼 수 있다.

즉, k가 작다는 조건이라면 매우 효율적인 정렬. 또한 카운팅 정렬은 배열을 사용하는 특성상, 정수라는 전제를 깔고 한다.

설명 출처 : https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#s-2.3.2

이미지 출처 : https://brilliant.org/wiki/counting-sort/

출처에 가면 애니메이션도 있어서 어떻게 돌아가는지 파악 가능함.

위의 이미지가 누적합까지 구하는 이미지이고

위에서 구한 누적합을 가지고 정렬을 시작한다.

0번 index (값 3) 를 정렬 배열 인덱스 2(배열의 순서는 0부터 시작하니 -1)에 넣어주고 누적합은 -1 해서 값 2

0번 index (값 2) 를 정렬 배열 인덱스 1(배열의 순서는 0부터 시작하니 -1)에 넣어주고 누적합은 -1 해서 값 1

이런식..

책에 있는 의사코드

C[0..k]를 새로운 배열로 한다.

for i = 0 to k

c[i] = 0

for j = 1 to A.length

C[A[j]] = C[A[j]] + 1

//C[i]는 이제 i와 같은 원소의 개수를 나타낸다.

//누적합

for i = 1 to k

C[i] = C[i] +[i-1]

//C[i]는 이제 값이 i보다 작거나 같은 원소의 개수를 나타낸다.

for j = A.lenght downto 1

B[C[A[j]]] = A[j]

C[A[j]] = C[A[j]]-1

의사코드를 C#으로 옮김

code : https://github.com/EomTaeWook/Algorithm/blob/master/Algorithm/Sort/CountingSort.cs

namespace Algorithm.Sort

{

    class CountingSort

    {

        public static List<int> Sort(List<int> unsortList)

        {

            return Sort(ref unsortList);

        }

        private static List<int> Sort(ref List<int> unsortList)

        {

            List<int> _countList = new List<int>();

            int max = unsortList.Max();

            _countList.AddRange(Enumerable.Repeat(0, max + 1));

            foreach (var value in unsortList)

                _countList[value]++;

            for (int i=1; i< _countList.Count; i++)

                _countList[i] += _countList[i - 1];

            List<int> _sortList = new List<int>(new int[unsortList.Count]);

            for(int i=0; i< unsortList.Count; i++)

            {

                _sortList[_countList[unsortList[i]] - 1] = unsortList[i];

                _countList[unsortList[i]]--;

            }

            return _sortList;

        }

    }

}