Сортировка подсчётом

В универе у меня была лаба: надо было отсортировать массив чисел, посчитать алгоритмическую сложность и количество сравнений.

📶 Обычно сортировки как выглядят? Проходишь по массиву, сравниваешь элементы друг с другом, меняешь местами по результатам сравнения. Если тебе нужно сравнивать каждый с каждым, то сложность алгоритма O(N²), это медленно 👎. Если реализовать более сложный алгоритм, каким-то образом бить массив на группы и работать уже с ними, то можно добиться сложности алгоритма O(N・log(N)), это быстро 👍.

🎬 В общем-то, ничего нового, визуализации алгоритмов сортировки с помощью народных танцев на ютубе все смотрели. Вот пример за N квадрат, а вот за логарифм.

🤔 А что, если я скажу, что сортировку можно написать вообще без сравнений? На лабе я выдал примерно такой код:

#include <stdint.h>
#include <string.h>

void count_sort(uint8_t *arr, size_t arr_len)
{
    // У нас в аргументах массив байт. Каждый байт может принимать 256 разных значений
    #define VALUES_CNT 256
    
    // Аллоцируем массив счётчиков, для коротких типов данных можно в статической памяти
    static uint64_t cnt[VALUES_CNT];
    memset(cnt, 0, sizeof(uint64_t) * VALUES_CNT);
    
    // Считаем вхождение каждого элемента в массив
    for (size_t i = 0; i < arr_len; i++)
        cnt[arr[i]]++;
        
    // Переписываем массив
    
    // Позиция в результирующем массиве
    size_t i = 0;
    // Проходим по массиву счётчиков
    for (size_t b = 0; b < VALUES_CNT; b++) {
        // Повторяем каждый элемент b в результирующем массиве c раз
        for (uint64_t c = 0; c < cnt[b]; c++) {
            arr[i] = (uint8_t)b;
            i++;
        }
    }
}

^ позапускать можно здесь

🤯 У препода от такого глаза на лоб полезли. “И сколько тут сравнений?” - спросил он. “Ноль” - ответил я 😎 И кстати, оно работает за O(N) - это даже быстрее, чем за логарифм. Но ограничений, конечно, много: сортировать так можно только массивы с малой областью допустимых значений.

🔥 В общем, думайте нестандартно, иногда даже самые глупые алгоритмы могут прекрасно работать. И обращайте внимание на ограничения, применимые ко входным данным. Это фундаментальная закономерность: чем больше ограничений можно применить ко входным данным, тем проще и эффективнее может быть алгоритм их обработки.

#theory #coding #algorithm