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

[wizzard]

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

а почему все считают, что сортировка произвольных данных 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 за наводку. Надо бы реализовать и потестить))

Comments

[slobin.livejournal.com]

Потому что первое -- оценка в худшем случае, а второе -- в среднем.

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

[wizzard]

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

[slobin.livejournal.com]

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

... cilre fo lo se srera ...

[slobin.livejournal.com]

Существует метод с гарантированным n*log(n) (метод пирамиды).

... noi ja'orgau ke'a lenu ke'a zekri te relsmu ...

[bik-top.livejournal.com]

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

[the-aaa13.livejournal.com]

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

[wizzard]

Блин, точно. *facepalm*

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

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

[slobin.livejournal.com]

В статье по ссылке распределение как раз задано: оно должно быть равномерным. Я очень сильно подозреваю (почти уверен), что для множества всех промежуточных результатов при методе вставки оно не соблюдается (даже если предположить, что таковым был исходный массив). Ну была же здесь уже аналогичная задачка... Проклятый эклер! :-(

... Identical to supernatural ...

[slobin.livejournal.com]

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

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

[wizzard]

В общем, да, я уже понял обе своих ошибки (про асимптотику и про то что insertion sort в чистом виде не ускоряется). Хотя, по идее, можно попробовать таким способом еще pivot у квиксорта выбирать.

[wizzard]

ой. про пивот - совсем фигню сказал, тьфу)))

[slobin.livejournal.com]

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

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

[wizzard]

Для совсем равномерного распределения, кстати, получается поиск за константное время. Индексирование массива, собственно)

[wizzard]

Но радикс, кажись, не inplace? (пошел смотреть википедию)

[bik-top.livejournal.com]

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

[slobin.livejournal.com]

Нет, не может, чушь порю. Стандартное доказательство того, что в худшем случае требуется не менее n*log(n) сравнений: элементы исходного массива могут быть переставлены n! (эн факториал) разными способами. Чтобы узнать, какой их этих способов правильный, мы должны задать не менее log_2(n!) бинарных вопросов. Из оценок для факториала (формула Стирлинга) получаем как раз n*log(n). Так что зря я на чудо понадеялся. ;-)

P.S. Ещё раз, это важно: подсчитываются (считаются за одно элементарное действие) сравнения, то есть операции, смотрящие на два числа и выдающие один бит информации. Если за одно элементарное действие считать что-то другое (например сравнение отдельных разрядов чисел), то результат будет другим. Но, поскольку поиск интерполяциями основан именно на сравнениях, результат к нему применим. А пересылки вообще не считаются.

... Октябрьский эль моделируется вином из одуванчиков ...

[slobin.livejournal.com]

В данном случае не важно: я утверждаю, что даже сравнений (игнорируя пересылки) потребуется не менее n*log(n) в худшем случае. Учёт пересылок может только ухудшить оценку. Это называется "энтропийная оценка": чтобы отсортировать массив, нам нужно добыть откуда-то не менее n*log(n) бит информации. Если единственным источником информации является сравнение на больше-меньше, то вот столько их и будет. Если разрешены другие источники информации (например, выделение отдельных битов из данных), то будет вот столько обращений к этим другим источникам.

... Какой я математик? Я флюктуация. ...

[slobin.livejournal.com]

Он, увы, не линейный. Ну то есть он линейный по размеру массива и линейный по длине элементов массива в битах, так что получается то же n*log(n). Я неаккуратно употребил слово в предыдущем комментарии.

... Transiit, quasi dolor, nox ...

[slobin.livejournal.com]

Хорошее наблюдение, да! А если мы априори знаем, что входной массив состоит из целых чисел от 1 до 10, то и результат сортировки можно просто взять и выписать. ;-)

... Одним движением бесшумно скользящего рычага ...

[wizzard]

Собственно, да.. Энтропия уменьшается - обработка упрощается...

[slobin.livejournal.com]

Ну и, с учётом выше (но позже!) сказанного, почему равномерность распределения всё-таки может помочь: если мы заведомо знаем, что элемент 0.99 не может оказаться в первой половине массива, то возможных перестановок сразу становится меньше.

... Я очень уважаю Леонида Андреевича ...

[wizzard]

Прошу заметить, что я не предлагал искать в неотсортированном, я предлагал оптимизировать операцию вставки.

Только вот структура данных, в которую можно вставлять и искать за менее чем log N, мне чегото не припоминается...

[slobin.livejournal.com]

Всё, сплю на ходу. В рамках этой дискуссии я насчитал уже, кажется, три (или больше?) существенно разных постановки задачи. И я сам их периодически путаю, пытаясь применить к одной результаты от другой. Получается чушь. :-( Прошу прощения, пошёл спать.

... Поймите меня хотя бы неправильно ...

[nicka-startcev.livejournal.com]

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

[thedeemon.livejournal.com]

> то же n*log(n)

Если n - число элементов, то с их размером оно не связано. Откуда здесь логарифм?

[wizzard]

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

[wizzard]

Длина элементов массива в битах, в предположении, что они разные (обычно сортируют все же разные элементы), асимптотически пропорциональна логарифму их количества.

[thedeemon.livejournal.com]

Враки.

[wizzard]

Покажите, как можно сделать массив из 2^50 разных 32битных интегеров?

[wizzard]

Ну или как сравнивать big интегеры за constant time.

[thedeemon.livejournal.com]

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

[slobin.livejournal.com]

Больше -- не меньше. Если я знаю, что весь массив состоит только из нулей и единиц, я сортирую его за линейное время.

... Сундук в паутине лихой голосил ...

[kodt-rsdn.livejournal.com]

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

[thedeemon.livejournal.com]

Правильно, и никакого логарифма там не будет.

[184467440737095.livejournal.com]

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

[wizzard]

Да, спасибо..

[wizzard]

О! Читаю.

[wizzard]

>> и что массив содержит все возможные элементы

Я этого не говорил.

>> Давайте будем сортировать строки, например.

Строка в данном случае от big integera ничем не отличается.

[wizzard]

Вот поэтому мы и говорим, что в массиве есть примерно равномерно распределенная выборка элементов из пространства возможных элементов.

[wizzard]

Хватит флеймить, тут штуку подсказали! :) http://wizzard0.livejournal.com/152387.html?thread=919619#t919619

http://hall.org.ua/hallservices/link/?link=hall:file:yijie.han-loglogn-sort.pdf:b949b7cf83&i=dl

[nicka-startcev.livejournal.com]

А это у всех методов зависит.

Если диапазон сравнительно небольшой, а элементов сравнительно много, то o(A)+o(B) будет намного быстрее, чем o(log(A))+o(A). (A - число элементов, B - диапазон).