Previous Entry Share Next Entry
2016-01

о сортировках

уважаемые товарищи!

а почему все считают, что сортировка произвольных данных inplace может выполняться за N log(N), если с 1985 1978 года у нас есть модификация бинарного поиска, работающая за log(log(N))?

ведь тогда, даже если взять банальную сортировку вставкой, асимптотика должна быть N*log(log(N)), или я чего-то недопонимаю?

UPD: блин, сортировка вставкой ведь еще двигать элементы должна, а в связном списке interpolation search невозможен.. надо сделать вариант Library sort и померять.

UPD2: а вот и N log log N сортировка от Yijie Han – yijie.han-loglogn-sort.pdf, спасибо 184467440737095 за наводку. Надо бы реализовать и потестить))


  • 1
slobin June 18th, 2010
Потому что первое -- оценка в худшем случае, а второе -- в среднем.

... Спой, Мэглор-скиталец, балладу мне ...


wizzard0 June 18th, 2010
Ну, у quicksort worst case N^2, если уж на то пошло.

the_aaa13 June 18th, 2010
Не то, чтобы в среднем, так как вероятностное распределение не заданно. Просто при (разумном) предположении эквидистантности. Зато в худшем случае можно и N^2 в сортировке заработать, что уж совсем не комильфо.

slobin June 18th, 2010
Хотя, если спросить "почему в среднем не получается"... Кажется, в этом же журнале уже был очень похожий вопрос, собрал довольно большую дискуссию. Там даже вычислительный эксперимент провели. Но формулировку вопроса я забыл. ;-) Сейчас, попробую сочинить иллюстрацию.

... cilre fo lo se srera ...


bik_top June 18th, 2010
Сомножитель log(log(N)) — это поиск места вставки. Сама же вставка предполагает сдвиг части отсортированных элементов вправо, а это есть N.

wizzard0 June 18th, 2010
Блин, точно. *facepalm*

А если Library sort ( http://en.wikipedia.org/wiki/Library_sort ) поюзать?

Хотя да, асимптотика будет уже гораздо ближе к N log N все равно...

slobin June 18th, 2010
О! Точно! Я это осознал, спутав термины: перепутал Radix Sort и Library Sort. ;-) Radix Sort вообще работает за линейное время, но у него основная операция -- НЕ сравнение, а выделение и сравнение отдельных цифр. Может быть, я был не прав, и на самом деле при условии равномерности распределения входных данных (то есть, грубо говоря, мы априори знаем, что примерно половина чисел лежит в интервале [0.0;0.5], а половина в [0.5;1.0]) тот же самый трюк сработает и на сравнениях.

... У Краггаша нет ни единого шанса! ...


slobin June 18th, 2010
Нет. Формальная "академическая" постановка задачи изменяет именно число сравнений, игнорируя все служебные операции. И я сильно подозреваю, что всё равно ничего хорошего не получится.

... Intrat et exit ut nil supra ...


bik_top June 18th, 2010
Проверил: у Кнута и у Кормена-Лейзерсона-Ривеста «нормальный» рассчёт асимптотики, а не «академический».

nicka_startcev June 19th, 2010
(цинично) Существует метод с гарантированным o(N), но у него есть ряд неприятных особенностей.

wizzard0 June 19th, 2010
Э не. У него это самое N зависит от диапазона значений ключей уже.

kodt_rsdn June 19th, 2010
Потому что NlogN - для любых абстрактных данных, над которыми определена операция сравнения.
А если мы знаем что-то большее, - например, что это целые числа, - то можем найти и более эффективные решения. Тот же радикс или подсчёт.

wizzard0 June 19th, 2010
Да, спасибо..

184467440737095 June 19th, 2010
а еще как-то вот так можно.
http://portal.acm.org/citation.cfm?id=509993

wizzard0 June 19th, 2010
О! Читаю.

  • 1
?

Log in

No account? Create an account