계수 정렬 알고리즘의 단계 안내

계산 주파수

구성 정렬 출력

void CountingSort(vector<int>& keys) {

    int max_key = *max_element(keys.begin(), keys.end());

    vector<int> bookkeeping(max_key + 1);

    for (int key : keys) bookkeeping[key]++;

    for (int i = 0, k = 0; i <= max_key; ++i) {
        for (int j = 0; j < bookkeeping[i]; ++j) {
            keys[k++] = i;
        }
    }
}

인덱스가 [0, i-1] 범위 내의 부기 서브 그룹은 키를 포함한다.
따라서 다음 인덱스 그룹의 i번째 요소는 부기 그룹에서 인덱스 i-1까지의 누적과 대응한다.부기와 다음 색인 그룹의 크기가 어떻게 같은지 주의하십시오.
마지막 단계는 다음 색인 그룹을 사용하여 정렬된 출력을 구축하는 것입니다.

next 인덱스로 정렬 출력 만들기

현재, 우리는 입력 그룹을 두루 훑어보고, 모든 키를 다음 인덱스 그룹의 인덱스로 사용해서 출력 그룹의 위치를 얻을 수 있습니다.
현재 요소가 출력 위치에 배치되면 키 인덱스의 다음 인덱스 요소가 증가합니다.이것은 항상 변하지 않습니다. 즉, nxt 인덱스의 i번째 요소는 다음 입력 요소가 정렬 출력에서 키 i의 위치를 나타냅니다.
일단 이 교체가 완성되면, 우리는 정렬된 출력 그룹을 입력 그룹으로 복사할 수 있다.

vector<pair<int, string>> CountingSort(vector<pair<int, string>>& items) {

    int max_key = max_element(items.begin(), items.end(), 
                  [](auto const& x, auto const& y) {
                      return x.first < y.first; 
                    })->first;

    vector<int> bookkeeping(max_key+1, 0);

    //counter[i] corresponds to the number of entries with key equal to i
    for (const auto& item : items) {
        bookkeeping[item.first]++;
    }

    //nextIndex[i] corresponds to the number of entries with key less than i
    vector<int> next_index(max_key+1, 0);
    for (int i = 1; i < next_index.size(); ++i) {
        next_index[i] = next_index[i-1] + bookkeeping[i-1];
    }

    vector<pair<int, string>> output(items.size());
    for (const auto& item : items) output[next_index[item.first]++] = item;

    return output;
}

공간 최적화

우리는 단독 넥스트 인덱스 그룹을 만드는 것이 아니라 메모리 공간을 절약하기 위해 부기 그룹을 직접 사용할 수 있다.이 점을 이해하기 위해 생각해 보자.

vector<pair<int, string>> CountingSort(vector<pair<int, string>>& items) {

    int max_key = max_element(items.begin(), items.end(), 
                  [](auto const& x, auto const& y) {
                    return x.first < y.first; 
                    })->first;

    vector<int> bookkeeping(max_key + 1, 0);

    //count keys frequency
    for (const auto& item : items) {
        bookkeeping[item.first]++;
    }

    //at the end each element is the index of the last element with that key
    std::partial_sum(bookkeeping.begin(), bookkeeping.end(), bookkeeping.begin());

    vector<pair<int, string>> output(items.size());

    //build sorted output iterating backward
    for (auto it = items.crbegin(); it != items.crend(); ++it) {
        output[--bookkeeping[it->first]] = *it;
    }

    return output;
}

범용 범위까지 확장

등록 정보

파이썬 구현

def countingSort(input):

    maxKey= max(input, key=lambda item:item[0])[0]

    bookeepingLength = maxKey+1
    bookeeping = [0] * bookeepingLength

    # Count keys frequency
    for item in input: 
        bookeeping[item[0]] += 1

    # at the end each element is the index 
    # of the last element with that key
    for i in range(1, bookeepingLength):
        bookeeping[i] += bookeeping[i-1] 

    output = [0] * len(input)

    # build sorted output iterating backward
    i = len(input) - 1
    while i >= 0:
        item = input[i]
        bookeeping[item[0]] -= 1
        position = bookeeping[item[0]]
        output[position] = item
        i -= 1

    return output

C# 구현

class CountingSort {

        private static int[] PartialSum(int[] input)
        {
            for (int i = 1; i < input.Count(); i++)
            {
                input[i] = input[i] + input[i - 1];
            }

            return input;
        }

        public static (int, string)[] CountingSort((int, string)[] items)
        {
            int max_key = items.Max(t => t.Item1);
            var bookkeeping = new int[max_key + 1];

            //count keys frequency
            foreach (var item in items) {
                bookkeeping[item.Item1]++;
            }

            //at the end each element is the index of the last element with that key
            bookkeeping = PartialSum(bookkeeping);

            var output = new (int, string)[items.Length];

            //build sorted output iterating backward
            for (int i = items.Length - 1; i >= 0; i--) {
                output[--bookkeeping[items[i].Item1]] = items[i];
            }

            return output;
        }
}

결론