algorithm
소계 계산

기본 정보 정렬 계산

계수 소트 는 객체의 키에 따라 정렬되는 객체 모음에 대한 정수 정렬 알고리즘입니다.

단계

1. 입력 배열 A 의 범위와 동일한 크기를 갖는 작업 배열 C를 생성 합니다.
2. C는 [X] 시간 (X)의 개수에 기초한 출연 할당하는 반복.
3. C 를 배열로 변환합니다. 여기서 C [x]는 배열을 반복하여 각 C [x]에 이전 값과 그 앞에 오는 C의 모든 값의 합을 할당하여 ≤ x의 수를 나타냅니다.
4. A를 거꾸로 반복하면서 각 값을 C에 기록 된 인덱스의 새로운 정렬 된 배열 B 에 배치합니다. 이것은 대해 수행되는 소정의 A [X]에 할당 B가 [C [A는 [X]] A [X] 및 감분 C에 [A는 [X]의 경우에 원래 정렬되지 않은 배열 중복 값이 있었다.

소계 계산의 예

보조 공간 : O(n+k)
시간 복잡성 : 최악의 경우 : O(n+k) , 최상의 경우 : O(n) , 평균의 경우 O(n+k)

Psuedocode 구현

제약 조건 :

1. 입력 (소트 할 배열)
2. 입력 요소 수 (n)
3. 0..k-1 (k)의 범위에있는 키
4. 수 (수의 배열)

의사 코드 :

for x in input:
    count[key(x)] += 1
total = 0
for i in range(k):
    oldCount = count[i]
    count[i] = total
    total += oldCount
for x in input:
    output[count[key(x)]] = x
    count[key(x)] += 1
return output

C # 구현

public class CountingSort
{
    public static void SortCounting(int[] input, int min, int max)
    {
        var count = new int[max - min + 1];
        var z = 0;

        for (var i = 0; i < count.Length; i++)
            count[i] = 0;

        foreach (int i in input)
            count[i - min]++;

        for (var i = min; i <= max; i++)
        {
            while (count[i - min]-- > 0)
            {
                input[z] = i;
                ++z;
            }
        }
    }

    public static int[] Main(int[] input)
    {
        SortCounting(input, input.Min(), input.Max());
        return input;
    }
}