Трехпутевая поразрядная быстрая сортировка

[VaalKIA]

И что, даже одного прогона теста написанного на коленке нам не покажут?!

[demist]

так пост об алгоритме, а не о реализации алгоритма :)

[VaalKIA]

Всё равно, теория должна подтверждаться практикой.

[alexeykuzmin0]

Сортировку строк еще очень удобно делать построением бора, правда, памяти больше съест

[saluev]

Разделяем массив на три части, сравнивая элементы с опорным по старшему разряду — на меньшие, равные и большие.

То есть речь не о двоичных разрядах?

[alexeykuzmin0]

Если сортировка строк или массивов — очевидно, нет. Да и обычную поразрядную сортировку, насколько мне известно, чаще реализуют в 65536-ричной системе счисления.

[saluev]

Мммм, бьют исходный массив на 65536 подмассивов?

[alexeykuzmin0]

Да, бить на много подмассивов как-то странно, но снизу вверх этот подход очень удобен. Если соберусь, напишу на днях статью

[hdfan2]

Пардон, а почему это память у QSort O(1)? O(log n) же, если аккуратно (и O(n), если в лоб).

[demist]

Все верно,O(log n) на стеке из-за рекурсивных вызовов.
Первым заметил alexeykuzmin0, спасибо

[ov7a]

Поправьте тогда уж и сложность работы трехпутевого алгоритма — в «поразрядной» части там же нужна дополнительная память.

[longclaps]

> сложность — O(nlogn)
> сложность алгоритма — O(n*k), k — число разрядов

Это часом не одно и то же?

[demist]

Не совсем. Разная асимптотика на одних и тех же данных(постоянном разряде) по числу элементов.
Допустим, у нас 2 разряда.
Тогда поразрядная сортировка будет O(2*n) [не совсем корректно, но так проще объяснить] — т.е., фактически, O(n)
А быстрая сортировка так и останется O(nlogn)

[saluev]

Собственно, вы привели главный аргумент против поразрядной сортировки. На массивах, заполненных редко повторяющимися числами, k ~ log n.

[demist]

вы не совсем правы. на массивах, состоящих из чисел большой разрядности, k может в разы превышать logn
число повторений чисел на k никак не влияет.

ну и асимптотики асимптотиками, но головой всегда надо думать :) бывает, что и алгоритмы с худшей асимптотикой работают быстрее в некоторых случаях, потому что константы огромны)
это такой маленький плевок в сторону фиб.куч

[ptyrss]

А можно поподробнее об оценке сложность алгоритма? Интересует зависимость от длины строк, просто если игнорировать этот параметр то у обычного QS будет такая же оценка в среднем (n log n) и выигрыш не так очевиден.

По поводу «Преимущество над быстрой сортировкой в том, что нам не требуется сравнивать элементы «целиком»» так строки крайне редко полностью приходится сравнивать, до первого различия обычно.

[demist]

Ну нас есть путь равенства первых символов.
Таким образом, мы «укорачиваем» строки, попавшие в данную часть на один символ — ведь мы и так знаем, что первый символ равен, его больше сравнивать не надо.
В обычном qsort пришлось бы каждый раз начинать с начала строки и бежать до первой разной буквы.

Т.к. массивы строк могут быть большими (по сравнению с размером алфавита), то на каждом шаге в раздел «одинаковые первые буквы» будет попадать достаточное количество строк, соответственно, мы неплохо сократим общее число операции сравнения букв.

[amakhrov]

Использовать radix, который требует дополнительную память, тоже не слишком мотивирует — строки могут быть большими

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