Сортировка подсчётом или почему этот способ игнорируют?

Введение в историю

Прошу без излишних эмоций реагировать на провокационное утверждение про игнорирование сортировки подсчётом всеми-всеми, ибо я не истина в последней инстанции, я не учился со всех возможных ВУЗах мира, поэтому я сужу только о себе и том, с чем мне приходилось сталкиваться. А заголовок чууутельку кликбейтный, да простит меня Интернет.

Теорию и технологию программирования я изучал в 90-е в провинциальном ВУЗе, но с весьма неплохим преподавателем, но даже от него я о таком способе сортировки не слышал. Не читал я о нём ни разу до, внимание!!! - 12 апреля 2022 года. Вот таким конём в вакууме я был. И самое интересное, что 12 апреля, как Юрий Гагарин, я "первым" для себя изобрёл этот тип сортировки. Занимался как всегда кодированием информации, сейчас балуюсь со словарями и их представлениями и мне понадобился простой (и быстрый) способ сортировки латинских букв - сиречь байтов.

Так как программирование для меня тема хоббийная, то я с определенной регулярностью что-то изобретаю и вопя "Эврика!" лечу в Интернет проверять. 20-25 лет назад, когда такое случилось впервые, находить что-то было весьма сложно, так как статьи были в основном на неправоверном инглише, поэтому статусом великого изобретателя я себя тешил иногда месяцами. Сейчас же поиск уже давно открытого занимает пару часов (если не минут).

Мне нужно было очень быстро получать из, например, ATLAS слово AALST, так же сортировать целиком файлы "книг". И поскольку байты - мой основной тип данных, то сортировка подсчётом отлично ложилась в основные концепции моих исследований. В частности программа вычисления энтропии файлов, написанная еще в 2020 году, уже пользовалась кодом по подсчёту задействованных байт, так что ядро мысли уже крутилось как волчок в моей голове. И когда я пару недель назад взялся (опять) за словари, то было уже делом времени - когда же волчок превратится в сверхновую.

На просторах интернета - и на Хабре и в Ютубе, по сортировке подсчётом информации весьма мало. С одной стороны там и рассказывать нечего, с другой - дурацкий пузырьковый метод описывают раз за разом, хотя он не несёт никакой практической пользы, он чисто академический и предназначен для демонстрации основного эффекта сортировки.

Реализация

Так как я перешёл на C# с Delphi, то код я дам именно на шарпе. Вот как раз обновился до 2022 студии и ринулся в бой. Скобочки везде оставил для комфортного чтения например новичками:

    public static void beSort()
    {
        byte[] sorted = File.ReadAllBytes(".\filename.txt");
        int[] map = new int[256];
        for (int i = 0; i < sorted.Length; i++)
        {
            map[sorted[i]]++;
        }
        int pos = 0;
        for (byte i = 0; i <= 255; i++)
        {
            if (map[i] > 0)
            {
                for (var x = pos; x < pos + map[i]; x++)
                {
                    sorted[x] = i;
                }
                pos += map[i];
            }
            if (i == 255) break;
        }
        File.WriteAllBytes("file_beSort.txt", sorted);
    }

Я не занимался никакими оптимизациями (напишите если там можно что-то улучшить) и сам код прямой как лом, но текущая производительность вполне устраивает, а вам будет во что меня ткнуть носом, всё же пусть красиво и быстро будет бонусом и подарком от специалистов в своём деле.

Чтобы было с чем сравнивать, я взял встроенную сортировку Array.Sort и выполнил работу в ней:

    public static void ArraySort()
    {
        byte[] sorted = File.ReadAllBytes(listfiles[0]);
        Array.Sort(sorted);
        File.WriteAllBytes("file_ArraySort.txt", sorted);
    }

Время работы 33 миллисекунды.

Идея сортировки подсчётом

1) Один раз проходим по данным и считаем число вхождений каждого байта, за счёт того что байт может содержать значения от 0 до 255 мы заранее можем создать массив map[256] и в качестве индекса счётчика использовать само значение в массиве байт, в коде это

            map[sorted[i]]++;

2) Так как исходный массив нам уже не нужен, то используем его для формирование сортированного массива

3) В цикле отсеиваем все значения map[] равные нулю - это байты, которые в файле не представлены

4) Запускаем цикл заполнения массива значением нужного байта i в количестве равном ранее подсчитанному значению из map[i], индексом положения указателя для записи данных используем временную переменную pos, которую всегда после заполнения части массива увеличиваем на значение из msp[i], то есть сколько байт записали, на столько и сдвинуть указатель

Скорость просто сногсшибательная. Тестировал на английской "20000 лье под водой" (20000 Leagues Under the Sea.txt) размером в 841313 байт. Время считал встроенными средствами

        Stopwatch sw = new Stopwatch();

что вылилось в 1 миллисекунду.

До заключения

Можно изменить код убрав if - следящий за границей байт на преобразование int в byte вот так:

        for (int i = 0; i <= 255; i++)
        {
            if (map[i] > 0)
            {
                for (var x = pos; x < pos + map[i]; x++)
                {
                    sorted[x] = (byte)i;
                }
                pos += map[i];
            }
            //if (i == 255) break;
        }

На результате это не сказывается:

C:\fc /b file_beSort.txt file_beSort_good_1ms.txt
Сравнение файлов file_beSort.txt и FILE_BESORT_GOOD_1MS.TXT
FC: различия не найдены

Пузырьком тот же файл сортировался 663 ТЫСЯЧИ миллисекунд.

Заключение

Не стал обсуждать аспект сортировки небольших данных, например я в начале упомянул сортировку отдельных слов. Там появляется мысль - не гонять для подсчёта все 256 возможных элементов массива map[], а сделать динамическую структуру, которая индексируется по ключу и расширяется по мере появления новых значений.

Лично я в таких ситуациях прибегаю к помощи Dictionary, но возможно у кого-то будет какая-то интересная идея на этот счёт. С удовольствием ознакомлюсь, а пока буду пользоваться прямым индексированием 256 элементов.

Логичным ограничением применения метода является использование таких типов данных, которые невозможно привести к байту. Например у вас в базе данных 10 миллионов записей вещественных чисел или большие целые числа например 32 или 64 битной разрядности.

Позволил себе метод назвать как beSort(), префикс - это мои инициалы и я ими пользуюсь при написании софта, пусть в сети остаётся след от моих безумств.

Спасибо всем дочитавшим до конца.

PS: в поиске картинки для публикации наткнулся на другое определение сортировки подсчётом - производится подсчёт количества раз, когда значение последовательности больше (или меньше) остальных значений. Это полностью отличается от того что написал я. Предлагаю разобраться вместе.