Comments 29
С виду добротно, хотя я только пролистал. Может быть ошибки и есть . Только вот предпоследний абзац было бы лучше поставить первым :-).
Быстрая, экономная, устойчивая...
Ещё есть экзотика вроде сортировки Хэна с асимптотикой N × log(log(N)), но её практически не используют из-за большого скрытого коэффициента.
А вообще у @valemakесть много интересных статей по самым разным сортировкам :)
Оказывается, существует также сортировка Хэна для вещественных чисел с асимптотикой N × sqrt(log(N)) по времени и памяти
Так как статья относительно свежая, и комментарии всего пол месяца ... Оставлю и свой комент
Я тут на днях изобрёл велосипед, который как оказалось ещё и сортировать массивы умеет, хотя изначально у меня стояли другие задачи
Едет этот велосипед в несколько раз быстрее "быстрой сортировки"
Сейчас я гоняю массированные тесты этого алгоритма, и в сравнение взял ещё две сортировки, помимо быстрой
К чему я всё это пишу: полез гуглить, и сходу не нашёл ничего, но чуть позже почитал немного про сортировку Хэна, и по описанию на вики - очень похоже, хотя по детальному изучению статей - сортировка Хэна какая-то "очень сложная", тут тебе и деревья, и хэши какие-то, описание с матаном - в общем действительно рокет-сайнс какой-то
А у меня всего два цикла верхнего уровня, и один вложенный как вспомогательный - для группировки дубликатов
практически не используют из-за большого скрытого коэффициента
Вот тут можете что-то по подробней ? Я бы хотел посмотреть "типовую" реализацию хотя бы псевдо-кодом, может выкладки какие
У меня же, сортировка как я уже написал, случилась сама собой, задачи были другие; моя реализация предоставляет кучу других плюшек, которые я преследовал изначально
А вы попробуйте посортировать всякие разные массивы. Отсортированные по возрастанию, по убыванию, молнией (10, 1, 9, 2, 8, 3, ...), состоящие из только одного повторяющегося значения, из двух случайно перемешанных, случайно сгенерированные.
И массивы надо побольше сделать (сотни тысяч элементов), ибо на маленьких хитрые алгоритмы уступают самым тупым, и библиотечные реализации используют только квадратичные алгоритмы, но из-за всяких дополнительных проверок и мишуры они будут чуть медленнее ручной наивной реализации какого-нибудь пузырька.
Может у вас какие-то ограничения дополнительные есть? Вроде: только небольшие числа в массиве? Тогда сравнивать надо не с быстрой стортировкой, а с сортировкой подсчетом.
В коментах нельзя картинки вкладывать
Я тестил массивы, сгенерированные случайно, до 10 000 элементов, но тест был поставлен таким образом, что каждый массив нужно отсортировать 1 000 раз - так я сглаживал всякие случайные факторы
Из ограничений - разница между минимальным и максимальным значениями. Но даже так алгоритм сохраняет логарифмическую асимптоту
Изначально предполагалось что числа должны быть только целые, но это ограничение можно обойти, если все числа привести к целым - помножить на pow(10,x) где x есть количество разрядов после запятой
Позже я пришёл к тому, что это некая вариация сортировки подсчётом O(n+k), но поведение асимптоты другое O(log(n)+k) или O(log(n)+n^k) я ещё точно с этим не определился, но суть в том что логарифм остаётся на любых интервалах данных. И такого я нигде не нашёл, только в своих замерах
Ещё одно ограничение - динамические массивы и отрицательные индексы, так что этот алгоритм не есть универсальный, или нужно пилить дополнительные обёртки
Задел хороший, но статья качеством похожа больше на черновик.
Исправьте, пожалуйста, грамматические ошибки. Ооочень бросаются в глаза при чтении. Кажется, их прям много (в первых 3-х предложениях уже).
И что это за графики? Что за величины у них по осям X и Y? В каких единицах?
Считаю совершенно обязательным хотя бы в "Списке алгоритмов" добавить наиболее принятое/популярное наименование метода на русском языке. А лучше - все "устоявшиеся" наименования метода - как ихнеязычные, так и русскоязычные.
Тогда совсем вот это получится https://programm.top/c-sharp/algorithm/array-sort/
А так вроде бы другая статья и собственный код реализации алгоритмов...
Столбец "Память" надо как-то развить: это память чего? Промежуточный буфер? Стек вызовов? Откуда для сортировок с обменом на месте там O(n)?
Что за a и k в таблице?
У Radix худшее время написанно O(n), а лучшее O(n x k), что выгляит больше. Т.е. в худшем случае сортировка получается быстрее чем в лучшем? Та же проблема в Counting.
Еще, этот k, похоже, разный в разных строчках. Так в Radix это должно быть количество разрядов в максимальном числе, когда как в Counting — это само максимальное число. Еще
Это всё-таки другая тема уже, ортогональная обозначенной.
На эту тему посмотрите доклад https://www.youtube.com/watch?v=XGtieBVI1lk&ab_channel=DotNext
Ну и другие доклады этого же товарища.
Оси на графиках нужно подписывать.
Не встретил упоминания АВЛ деревьев -- расстроился.
Спасибо, хорошая подборка в одном месте. На мой взгляд, не хватает информации о применимости в том или ином случае.
Спасибо. Отличная подборка.
Забыли Bozo сорт, сортировку перестановками (Perm sort) и сортировку Бабушкина :)
Автор проделал большую работу. Так а вывод-то какой?
Я хочу сортировать... какой алгоритм мне использовать? Я так понимаю, есть следующие пользовательские условия/требования/ограничения.
1. Количество элементов, на 100 элементах выгоднее один алгоритм, на 100 млн - другой.
2. Возможность параллелизации. (Видеокарты у всех же нынче простаивают).
3. Объем памяти - он есть в таблице, дают ли алгоритмы требующие больше памяти существенный выигрыш во времени?
Спасибо за труд! К уже сказанному выше про подпись осей графиком и какие-то общие выводы, есть и мои собственные замечания:
Хотелось бы описания поуникальнее или поподробнее. С пояснением, чем же конкретная сортировка знаменита и какова область её использования. Сами сравните описание Bubble и Comb. По описанию Comb я вообще не понимаю в чём её плюс и отличие по сравнению с Bubble - слова одни и те же. Да, можно почитать код и разобрать его. Но в таком случае, какой смысл описаний? Ещё пример:Coctail против Shaker - про оба написано, что каждый проход меняется порядок. А в чём их особенности? Почему они по разному названы?
Местами текст выглядит неоконченным или просто неясно сформулированным. Вот возьмем последнюю строку из первого абзаца про Shell:
Шелл предлагал использовать
Возможны и другие смещения, но 
всегда.
Почему "Hi = 1 всегда?" Что это значит?Все сортировки выглядя полезными и применимыми в разных ситуациях. Даже пузырьковая. Но что в этом списке делает bogosort? Если уж впихивать совершенно неэффективные алгоритмы, которые написаны чисто для прикола, то их, во-первых, больше чем одна, во-вторых, по моему мнению, им место в отдельном посте с описанием других "не от мира сего" сортировок.
Что за графики без подписей?! ?
Напомнило
В сортировке Tree в методе TreeNode::Insert не хватает балансировки. Без нее сложность построения дерева из уже отсортированного массива получается O(n^2), а не как указано O(n * log(n)).
Алгоритмы сортировки и их производительность