How to become an author
Search
Write a publication
Pull to refresh

Comments 29

Я бы сказал наконец-то!
Total votes 1: ↑1 and ↓0+1
Спустя 40 лет после первого результата? :D
Total votes 7: ↑7 and ↓0+7
«В поисках идеальной сортировки» ))))

Интересно видеть насколько Вы продвинулись по сравнению с прошлыми наработками! Жаль, что Вы не описывали промежуточные этапы (объём кода ж таки со 100 строк вырос во все 400) — очень увлекательно бы понаблюдать как рождаются алгоритмы.
Total votes 1: ↑1 and ↓0+1
С тех пор у меня была ещё одна реализация in-place merge сортировки, которая процентов на 20-30 обгоняла quicksort, но в ней использовался небольшой дополнительный массив, и я решил, что незачем её показывать.
А идея там была очень простая. Если в массиве длины N есть отсортированные куски длиной X и (N-X)/2, то мы их можем слить за N сравнений и обменов, используя оставшиеся (N-X)/2 элементов в качестве буфера. В результате длина неотсортированного куска уменьшится вдвое. Сортируем его половину и повторяем процесс :) Максимальное число сравнений — 2*N*log(N), что вдвое хуже чистого MergeSort и сравнимо с QuickSort. Если последние 256 элементов сортировать с помощью дополнительного массива, то мы выигрываем 8*N операций, и на достижимых размерах массивов QuickSort отдыхает…
Была ещё реализация RadixSort для 96-битных чисел, которая обгоняла QuickSort в 6 раз, но там тоже ничего особо интересного — те, кого алгоритмы интересуют, легко бы нашли её сами. А остальные и не поймут, зачем гнаться за константой :)
Total votes 5: ↑5 and ↓0+5
Для quicksort это среднее время. У алгоритма, который нашел автор, n*log(n) — худшее время.
This comment wasn’t rated yet0
Среднее для классического quicksort. Для тюнингованного quicksort, который я привел, n*log(n) — worst-case expected-time bound. Поправьте, если ошибаюсь.
This comment wasn’t rated yet0
Так в вашем же документе написано, что именно среднее время — n*log(n). И что это эквивалентно случайному перемешиванию массива и выдаче этого в обычный quicksort.
This comment wasn’t rated yet0
Насколько я понял, это среднее время для любого (даже самого неудачного) входного массива. Quicksort можно написать так, что он даст в среднем n*log(n) для любого массива с попарно различными элементами, но свалится в n^2, если все элементы окажутся одинаковыми. Для такой реализации worst-case expected-time окажется n^2, хотя в среднем, по всем массивам, время по-прежнему будет n*log(n).
Total votes 1: ↑1 and ↓0+1
На самом деле, «свалится в n^2, если все элементы окажутся одинаковыми» корректнее заменить на «всегда найдется пример».

В quicksort многое зависит от того, как делать разбиение. Например, есть способы делать разбиение таким образом, что массив одинаковых элементов будет обрабатываться за N шагов.
Total votes 2: ↑2 and ↓0+2
А как вы его сделаете устойчивым? Даже среднее время n*log(n) для устойчивого алгоритма без дополнительной памяти было бы интересным результатом.
This comment wasn’t rated yet0
Это правда, тут проблема. Можно сделать устойчивым, но время уже не будет n*log(n).
This comment wasn’t rated yet0
Но максимальное-то у randomized quicksort все равно n2…
This comment wasn’t rated yet0
When are you guys gonna do bogosort?
Total votes 1: ↑1 and ↓0+1
Почему вы не хотите выложить исходники на GitHub или хотя бы Bitbucket, Codeplex, SourceForge?
Total votes 4: ↑4 and ↓0+4
Основная причина в том, что сейчас я не чувствую в себе достаточно сил на освоение новой экосистемы. Думал изучить что-нибудь такое за последний месяц, но свободных ресурсов не нашлось :(
Total votes 2: ↑1 and ↓10
Ну с учетом того, какого уровня статьи вы пишете, освоить, например, GitHub вообще можно быстро и не представляет никаких сложностей, особенно просто для цели запостить код :)
Total votes 1: ↑1 and ↓0+1
Спасибо. Добавлю.
Total votes 1: ↑1 and ↓0+1
фактически, он написан на C — надо только перенести описания переменных в начало функций
Объявления переменных где попало, в том числе в инициализации цикла for, ещё в C99 разрешили. Другой вопрос, что Microsoft этот стандарт игнорирует.
Total votes 1: ↑1 and ↓0+1
Описание сражений с документацией напомнило, как я в студенческие годы успешно решил задачу коммивояжёра алгоритмом за N^3 итераций.
This comment wasn’t rated yet0
К счастью, в некоторых более поздних работах удалось найти способ, позволяющий обойти эту неприятность


Не могли бы вы дать ссылку на работу, в которой описан «чистый» вариант?

Спасибо!
This comment wasn’t rated yet0
Там хитрая ситуация. В последующих работах решают задачу устойчивого слияния двух фрагментов за линейное время. Понятно, что из возможности такого слияния следует возможность сортировки, но не факт, что такой путь будет самым простым.
Я поискал ссылки на статью о сортировке, в надежде, что кто-нибудь увидел в ней ошибку. Таких не обнаружил, но наткнулся на вот эту работу:

Viliam Geffert; Jyrki Katajainen, Tomi Pasanen, Asymptotically efficient in-place merging, Theoretical Computer Science 237 (2000) 159–181
www.sciencedirect.com/science/article/pii/S0304397598001625

Алгоритм у них сложный и запутанный, поэтому я просматривал его только чтобы понять, пользуются ли они сортировкой блоков, и как различают блоки из первого и второго фрагментов. Ну, и увидел, что они в одной из веток набирают столько ключей, чтобы хватило и на буфер обмена, и на метки блоков. А большего мне и не надо было :)
Total votes 1: ↑1 and ↓0+1
Спасибо!

Ошибку, возможно, не обнаружили, потому что алгоритм не практичный. Наверное, никто особо не хотел его реализовывать.

А может, обнаружили, но забили. Дыры в алгоритмах иногда проще найти практику, нежели теоретику. Но практики не сильно заинтересованы в публикациях.

У меня коллеги как-то реализовывали алгоритм (точнее, целый комплекс алгоритмов) из одной очень продвинутой и котируемой американской диссертации.

В результате применения этих наработок в рамках большого промышленного проекта, выяснилось, что в диссертации огромная дырень, из-за которой вся диссертация должна лететь в трубу. Опровержения они не выпустили. Наверное, потому, что не было конструктива: как латать дыру, никто не знал. Писали автору, но он проигнорировал их письма :)
This comment wasn’t rated yet0
Этап B2 можно сильно ускорить. Пока число G достаточно мало, может случиться так, что (K/2)^2>=2*G. В этом случае мы можем разделить множество ключей пополам, и половину использовать в качестве буфера обмена (а вторую половину — как ключи), и сливать фрагменты с помощью более быстрого метода из A2. А на обмены без буфера перейти в самом конце, когда G приблизится к размеру массива.
Чем больше у нас разных ключей, тем дольше работает слияние без буфера, но и тем дольше мы можем обойтись без него.
Эксперименты показывают, что в самом неблагоприятном случае из тех, что я проверял, алгоритму требуется не больше, чем 1.7*N*log2N сравнений и 2.2*N*log2N обменов (при N>1000000, на случайных данных с заранее заданным числом различных ключей). Хотя я ещё поищу случай похуже (например, 2^k-1 различных ключей — там алгоритму будет очень плохо).
Total votes 1: ↑1 and ↓0+1
Sign up to leave a comment.

Articles

Show the best of all time
Unlock dark mode

Your account

Sections

Information

Services

Support
© 2006–2024, Habr