Комментарии 23
Сортировать long int не хватит никакой памяти ;)
Ранжируем сначала по старшим битам (например разбив по 8 бит), а затем рекурсивно каждый интервал.
Например?
Есть у нас shortint:
0000, 0001,0100,0101
После прохода счётчика по старшим байтам
Counters[] = {2,2}
Как восстановить интервал для рекурсивной сортировки?
Для объяснения по вашему же примеру лучше разбить по два бита. Если для решения задачи использовать связанные списки, то выделяем дополнительный массив (размером с входной массив) в нем мы храним индекс следующего элемента (или -1 если конец списка). В индекс-массиве из 4 элементов храним первые элементы списка. После первого прохода получаем такое [[0, 1],[-1],[1,2],[-1]]. Каждый подсписок сортируем рекурсивно. Собственно radix-sort позволяет перебирать группы бит как от старших к младшим, так и от младших к старшим, там не принципиально получается.
Вот вы и изобрели radix sort. Правда хитрость в том, чтобы не сортировать интервалы рекурсивно, а сортировать сначала по младшим битам, потом по средним и в конце — по старшим. Если один этап сортировки сделать стабильным (что очень просто), то в итоге данные будут отсортированны правильно.
В сортировках вообще можно очень большого прогресса добиться в отдельных частных случаях.
Ваш метод экспоненциально зависит по используемой памяти от длины ключа и эффективен по времени только в том случае, когда ключи плотно заполняют множество своих возможных значений. Если у вас дело сведётся к поиску нескольких единичек среди миллиардов и триллионов нулей, то пузырьковая сортировка будет эффективней.
Не читал я о нём ни разу до, внимание!!! - 12 апреля 2022 года. Вот таким конём в вакууме я был.
С подключением!
Сортировка подсчётом годится только для значений, которые можно генерировать, и типы которых характеризуются небольшими кардинальными числами (это число значений типа). Числа типа int8,int16, с натяжкой int32 ещё подходят под это ограничение, но произвольные объекты, типа строк или записей в БД - нет.
Вычислительная сложность сортировки подсчётом O(N), а у продвинутых гибридных методов наподобие TimSort - те же O(N) в некоторой доле случаев (O(N logN) в общем случае). Зачастую разница невелика, поэтому сортировка подсчётом используется крайне редко. Я не видел эту сортировку в стандартных библиотеках, да и на практике за много лет применять её мне не приходилось.
Пузырьковая сортировка имеет асимптотическую оценку сложности O(N^2). Самые быстрые алгоритмы сортировки, HeapSort например (сортировка на бинарных деревьях), имеют асимптотическую сложность O(NlogN). Это означает, что все они полиномиальны по сложности. Есть алгоритмы, которые предполагают сортировку отдельных массивов данных с их последующим слиянием. Алгоритм, который Вы рассматриваете, при небольшом массиве сортируемых данных может потребовать очень большой памяти. Если на примере чисел, то всё зависит от того, из какого диапазоне выбираются эти числа.
Всё равно непонятно, зачем у статьи минус. Да, это велосипед. Да, пригоден только в частном случае. Но для частного случая подходит идеально, и честно изобретён.
randomsimplenumber, спасибо за объективный взгляд на статью. Мне кажется вы верно уловили мою мысль.
Druj, не согласен что это сжатие/восстановление, иначе таким макаром можно ASCII таблицу назвать способом сжатия любого текстового файла. Так как этот метод сортировки имеет явные ограничения, то никакой магии тут нет. Вы же не пытаетесь обвинять пузырьковый метод несостоятельным например на 1Тб данных? Мои идеи схожи с тем как работают архиваторы и вот в чём - разные алгоритмы дают разный результат по соотношению скорость/степень сжатия, что приводит к тому, что указывая ключ "-mX" например от 0 до 5 вы выбираете алгоритм сжатия, а не вариацию какого-то одного алгоритма. Например у Мэтью Махони в zpaq это выглядит так:
Method Compress Decompress Algorithm
1 128 MB 32 MB LZ77
2 450 MB 128 MB LZ77
3 450 MB 400 MB LZ77+CM or BWT
4 550 MB 550 MB LZ77+CM, BWT or CM
5 850 MB 850 MB CM
И очевидно что на разных данных методы 4 и 5 могут делить между собой первенство. Или так - выбор метода неразрывно связан с типом данных, а не со степенью сжатия. Простой пример - создаю файл в 1 мегабайт с рандомным расположением всего двух разных символов "≈с≈≈с≈сссс≈≈≈" (и так 1 Мб). Пакуем zpaq с ключами -m4 и -m5, в итоге 4 метод - файл 4.8 Кб, а пятый - 7.3 Кб. Разговоры в духе "мало кому нужно" не имеют смысла, так как при изучении методов и алгоритмов мы изучаем почти всё до чего можем дотянуться и моё умеренное негодование как раз и вызвано тем, что такой способ никак не представлен, по крайней мере широко, как тот же пузырьковый, хотя именно решение частных задач в определённых контекстах может происходить совершенно разными способами.
vadimr, не проверял, может чуть позже и проверю, например на миллиарде это не составит труда сделать, но на мой взгляд линейное масштабирование этого метода приведёт и к линейному росту сложности. А так как в "моём" методе нет никаких сравнений, то по сути он отработает как O(n), а пузырьковому как минимум потребуется O(2n) даже всего на одной единице среди миллиарда нулей.
Akon32, я не вижу как этот метод может быть хуже того же пузырькового, например в виде статьи в учебнике или в виде примера на Википедии с данными - "0,7,4,6,6,3,32,5,63,3,4,6,6,4,3,5,6,6,4,3,2", и так же никому не помешает в описании плюсов и минусов указать всё что вы написали, наравне с такими же данными для любого другого метода. Я же не предлагаю всё бросить, переписать все библиотеки во всех языках и начать пользоваться этим способом. Но как минимум я, работая с текстовыми файлами и словарями вижу для себя огромный буст от такого метода, потому что впереди у меня задача по сбору статистики по некогда выгруженной библиотеки Машкова, это текстовых файлов на 700 Мб в виде архивов. И я совсем не хочу чтобы прогон тестов на таких объемах упирался в сортировку. Мне и кроме неё много чего делать нужно будет. Поэтому я в этом методе вижу отличное логическое продолжение своей первой статьи, хороший академический метод (поверьте, из тех кто читал описание TimSort весьма мало тех кто реально понимает что там происходит), вы же понимаете что сортировку пузырьком и подсчётом можно объяснить даже школьникам. Я сам всегда что-то сортировал стандартными либами, это просто и удобно, но изобретение чего-либо - это процесс творческий и часто весьма далёк от практического применения, например двигатель Стёрлинга изобрели 200 лет назад, но практически мало используют из-за массы ограничений, при этом само изобретение просто шедевральное и простое.
Резюмируя свой опус скажу, что в первую очередь я предлагаю этот метод к рассмотрению как учебный - безумно простой в реализации. Во вторую - как метод при работе с конкретными данными, как в моём случае с текстом. В третью очередь - это просто интересная разминка для мозга, так как ещё нужна реализация с динамическим массивом map[] для коротких массивов - зачем плодить сущность в 256*sizeof(item) если нужно отсортировать слово длиной в 8 байт? Нужна реализация для String, которая в C# должна минимизировать количество операций со строками. Возможно всё это имеет смысл оформить уже второй частью статьи.
В любом случае спасибо всем за обсуждение.
пузырьковому как минимум потребуется O(2n) даже всего на одной единице среди миллиарда
Асимптотическая сложность сортировки методом «пузырька» — O(N^2). На всякий случай ещё и напишу: N в квадрате, где N — мощность сортируемого массива данных (количество объектов в нём). Кстати, оценка O(2N) смысла не имеет. Поскольку символ Бахмана так устроен, что учитывает мульпликативные константы, которые могут отличаться для различных реализаций алгоритма, зависеть, например, от платформы и пр.
Так как я могу оставлять комментарии только раз в сутки, то здесь отвечу на ваши оба комментария.
1) Когда я написал O(2n) я имел в виду два умножить на n, без квадратов. Связано это с тем что пузырёк с оптимизациями завершает работу если нет перестановок, поэтому если в огромном массиве из нулей поместить одну единицу, то цикл сортировки пройдёт два раза по n - первый раз угнав единицу в конец массива, а второй раз - убедиться, что перестановок нет. Если же массив уже отсортирован, то это будет O(n). Поэтому сложность пузырька варьируется от O(n) до O(n^2).
2) Особенность моего метода в том, что количество ключей заведомо сильно меньше числа записей в БД, поэтому как очевидное развитие метода в конце статьи я и упомянул - использовать динамический массив ключей (1, L) вместо статического. Из этой предпосылки о формируется сложность O(N), например для моего эксперимента размер текстового файла был больше L в 2500 раз. И сейчас, работая с другими файлами я провожу тесты Array.Sort, Bubble Sort и beSort на файлах в 10 Мегабайт и beSort стабильно быстрее. Есть только один вариант, где Bubble Sort даже чуть быстрее - это уже отсортированный массив. Тут очевидно что N проходов с одним if() который никогда не срабатывает - будет быстрее, чем N операций инкремента ячеек памяти с формированием выходного массива. Моя текущая реализация загружает всё в память, что например не подойдёт для сверх больших файлов, можно написать реализацию таким образом, что данные будут читаться постепенно, а результат постепенно же записываться. Поэтому резервирование памяти упирается в размер массива и скорее равно L(LOG2(N)), например для 256*sizeof(ulong) в x64 сборке на C# мы имеем массив в 2048 байт, а допустимый размер файла в 1,844674407370955e+19 байт (или 4 миллиарда в квадрате, а такие объемы данных на сегодня есть разве что у гугла или амазона, только их все сразу никому сортировать в голову не придёт). То что касательно необходимости обнуления массива сумм, то для C# это не проблема, система сама это делает, а для динамической реализации обнуление можно делать только на момент инициализации, так как нет статичного массива.
PS: хочу отметить что beSort не требует дополнительной памяти для отсортированного массива, ему нужен только массив сумм L(LOG2(N)) байт.
О(2n) не бывает ;). Эта запись эквивалент О(n).
Уважаемый автор! Продолжаете упорствовать и пришло время вас немного пожурить. Вы не понимаете смысла асимптотической оценки сложности «O-большое» или «символа Бахмана», как эту оценку ещё называют по имени математика, который её ввёл. А ведь про это должен знать каждый, кто прослушал и усвоил университетский курс computer science. Здесь уже несколько комментаторов отметили сей печальный факт. Вместо того, чтобы обратиться к учебнику и всё тщательно обдумать, Вы продолжаете твердить своё. При этом Вы не понимаете, что вычислительную трудоёмкость — этот термин принят в русскоязычной литературе вместо «сложность» (прямой перевод англоязычного термина «complexity») — оценивают в «худшем» случае, редко «в среднем» (для этого нужны веские причины), но уж точно не подбирают параметры так, чтобы обосновать преимущество алгоритма. Что касается каких-то весьма частных случаев, то они малоинтересны. И на это вам тоже указывали. Кто из нас не предлагал эффективного решения отдельных задач с сильными ограничениями? Интересны универсальные методы с гарантированной асимптотической оценкой. В общем писать программы — это хорошо, конечно, но как завещал Дональд, отец наш Кнут, надо к ещё и к источнику знаний припадать время от времени, а лучше всего математику учить. Тогда и вопросов лишних не будет, а у некоторых мировоззрение даже выправляется.
1) Когда я написал O(2n) я имел в виду два умножить на n, без квадратов. Связано это с тем что пузырёк с оптимизациями завершает работу если нет перестановок, поэтому если в огромном массиве из нулей поместить одну единицу, то цикл сортировки пройдёт два раза по n - первый раз угнав единицу в конец массива, а второй раз - убедиться, что перестановок нет. Если же массив уже отсортирован, то это будет O(n). Поэтому сложность пузырька варьируется от O(n) до O(n^2).
К вопросу об ограничениях и частных случаях. А если предположить, что только на одной позиции (неизвестной заранее) имеется отличное от нуля значения, а во всех остальных позициях расположены нули и это установленный факт? Тогда потребуется n-j сравнений и перестановок, где j — позиция, на которой находится это самое ненулевое значение. Иными словами, n-1 таких операций в худшем случае. А если заранее известно, на какой позиции находится это ненулевое значение, то сортировка вообще не нужна? Вы хотя бы интуитивно понимаете, что это вот всё вообще ни о чём?
Ваш алгоритм сортировки, как я его понимаю, поправьте если что не так, устроен следующим образом. Пусть имеется 
объектов, которые необходимо отсортировать в порядке неубывания. Например, это могут быть записи в базе данных. Сортировка осуществляется по ключу, а именно по содержимому некоторого позиционно фиксированного поля в пределах каждой записи и это поле всегда существует. Пусть ключ — это натуральное число. Отмечу, что алгоритм обобщается на целые числа. Ключ принимает значение из диапазона 
. Заранее величины ключа не известны и можно исходить только из минимально и максимального значений указанного диапазона. Это означает, что необходимо зарезервировать 
бит памяти. Назовём ячейкой отдельную порцию 
бит. Тогда для сортировки нам понадобится 
ячеек памяти с прямым доступом и значение ключа — это относительный адрес некоторой ячейки. Для начала мы выполняем подготовительную операцию обнуления — заносим в каждую ячейку значение 0. Затем приступаем непосредственно к сортировке: 1) считываем значение ключа из записи; 2) используем это значение для перехода к нужной ячейке (смещением относительно базового адреса) и увеличиваем её значение на 1 (это счётчик вхождений). Когда все ключи обработаны, нам надо получить результат сортировки. Для этого мы проверяем значение каждой ячейки и формируем отдельный список, в котором напротив значения ключа располагается значение счётчика. Дело сделано. Понятно, что асимптотическая сложность такой сортировки не 
, а 
. При этом, очевидно, что в худшем случае
Если 
— это некоторая экспонента, то асимптотическая сложность такого алгоритма сортировки перестаёт быть полиномиальной.
Полагаю, что минусуют Вас в большей степени за тот самый провокационный заголовок. Мотивация привлечь читателя любой ценой объективно понятна, однако такие методы могут вызывать естественное раздражение :) Лично меня статья вместе с комментариями к ней сподвигла освежить в памяти разные методы сортировки, оставив смешанные чувства: отрицательные от финта с заголовком и положительные от содержания самой статьи.
Сортировка подсчётом beSort или как я изобретал велосипед?