About

Сортировка подсчётом(Черпачная) (англ. Counting sort) — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Если на вход поддана некоторая последовательность чисел, то операции будут проводиться со всеми числами, начиная от самого маленького числа из этого массива и заканчивая самым большим. Учитывая даже те, что не содержатся в этой последовательности.

Нахера Зачем это вообще?

Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Например, если вы хотите отсортировать людей (звучит странно, но наша компания против насилия), работающих в вашей компании, по их возрасту. Или же если вам, как организатору ЕГЭ, потребовалось отсортировать позорные результаты огромного количества сдающих в вашем районе. В этом случае разброс баллов будет всего от 0 до 100, а вот сдающих очень много.

Приступим

(Примечание: в анимациях не используется оптимизация -min)

Если рассматривать эту сортировку с точки зрения теории, то звучит все намного сложнее, чем есть на самом деле. Процесс её можно разбить на 3 цикла (есть еще 4-ый, но он никакой смысловой нагрузки не несет). Но перед тем, как перейти к первому циклу, следует уделить внимание тому, с какими данными заходить в метод сортировки. Итак, нам понадобится сам массив, его длина, а также его max и min элемент.

void countingSort(int arr[], int len, int min, int max){...}

Что-ж, начнем.

Первый цикл.

Первым делом мы должны подготовить тот самый интервал чисел от минимального значения до максимального, который мы упомянули в самом начале. Для этого создадим массив размером max-min+1, обнулим и обзовём его массивом счетчиков.

int counts[max-min+1];
memset(counts, 0, sizeof counts);//обнуление массива через динамику за n/64 операции.

Теперь проходим по нашему исходному массиву и каждый раз увеличиваем на единицу (i-min)-тый элемент. Думаю, цель вычитания min в данном случае очевидна: если min = 1 000 000 000, а max = 1 000 000 010, например.

for(int i = 0; i < len; i++){
    counts[arr[i]-min]++;
}

Второй цикл

Если вы знакомы с Radix Sort, то наверняка сразу поймете, в чем суть следующего шага. В противном случае - не страшно, сейчас разберемся.

Итак, нам нужно пройтись по всему массиву счетчиков и к каждому следующему элементу прибавлять предыдущий. Сделано это для того, чтобы массив счетчиков, который хранил количество повторов того или иного числа, теперь начал нести немного другую информацию, а именно индексы, на которых будут располагаться соответствующие числа в отсортированном массиве.

for(int i = 1; i < max-min+1; i++){
    counts[i] += counts[i-1];
}

Третий цикл.

В последнюю очередь мы проходим по каждому значению исходного массива, по этому индексу в массиве счетчиков получаем значение, уменьшаем на 1 и кладем наш элемент в ячейку с этим индексом в новый массив. (не забываем -min)

int finalArr[len];

for(int i = len-1; i >= 0; i--){ //можно и с другой стороны, но сделаем так для соответствия анимации
    finalArr[--counts[arr[i]-min]] = arr[i];
}

Четвертый (завершающий) цикл.

Наличие этого цикла зависит от языка программирования и реализации, но мы предпочли его добавить для полноты картины. Мы просто копируем значения отсортированного массива в исходный.

for(int i = 0; i < len; i++){
    arr[i] = finalArr[i];
}

Заключение

void countingSort(int arr[], int len, int min, int max){

    int counts[max-min+1];
    memset(counts, 0, sizeof counts);

    for(int i = 0; i < len; i++){
        counts[arr[i]-min]++;
    }

    for(int i = 1; i < max-min+1; i++){
        counts[i] += counts[i-1];
    }

    int finalArr[len];
    for(int i = 0; i < len; i++){
        finalArr[--counts[arr[i]-min]] = arr[i];
    }

    for(int i = 0; i < len; i++){
        arr[i] = finalArr[i];
    }
}

В итоге, при помощи всего 3-х циклов и 2-х вспомогательных массивов мы смогли отсортировать исходный. Алгоритм прост в реализации, обладает недостатками в виде его непригодности для сортировки слишком больших в разбросе чисел и довольно неплохими достоинствами в виде хороших времени работы и сложности. Немного о них.

Первый и третий цикл работают за O(len), второй цикл за O(max-min+1), также можно учесть незначительную операцию обнуления массива счетчиков за O((max-min+1)/64).

Итоговая трудоемкость алгоритма и по времени, и по памяти, равна O(len + max - min + 1).

Характеристика алгоритма.