Комментарии 18
И что, даже одного прогона теста написанного на коленке нам не покажут?!
Сортировку строк еще очень удобно делать построением бора, правда, памяти больше съест
Разделяем массив на три части, сравнивая элементы с опорным по старшему разряду — на меньшие, равные и большие.То есть речь не о двоичных разрядах?
Пардон, а почему это память у QSort O(1)? O(log n) же, если аккуратно (и O(n), если в лоб).
Все верно,O(log n) на стеке из-за рекурсивных вызовов.
Первым заметил alexeykuzmin0, спасибо
Первым заметил alexeykuzmin0, спасибо
> сложность — O(nlogn)
> сложность алгоритма — O(n*k), k — число разрядов
Это часом не одно и то же?
> сложность алгоритма — O(n*k), k — число разрядов
Это часом не одно и то же?
Не совсем. Разная асимптотика на одних и тех же данных(постоянном разряде) по числу элементов.
Допустим, у нас 2 разряда.
Тогда поразрядная сортировка будет O(2*n) [не совсем корректно, но так проще объяснить] — т.е., фактически, O(n)
А быстрая сортировка так и останется O(nlogn)
Допустим, у нас 2 разряда.
Тогда поразрядная сортировка будет O(2*n) [не совсем корректно, но так проще объяснить] — т.е., фактически, O(n)
А быстрая сортировка так и останется O(nlogn)
Собственно, вы привели главный аргумент против поразрядной сортировки. На массивах, заполненных редко повторяющимися числами, k ~ log n.
вы не совсем правы. на массивах, состоящих из чисел большой разрядности, k может в разы превышать logn
число повторений чисел на k никак не влияет.
ну и асимптотики асимптотиками, но головой всегда надо думать :) бывает, что и алгоритмы с худшей асимптотикой работают быстрее в некоторых случаях, потому что константы огромны)
это такой маленький плевок в сторону фиб.куч
число повторений чисел на k никак не влияет.
ну и асимптотики асимптотиками, но головой всегда надо думать :) бывает, что и алгоритмы с худшей асимптотикой работают быстрее в некоторых случаях, потому что константы огромны)
это такой маленький плевок в сторону фиб.куч
А можно поподробнее об оценке сложность алгоритма? Интересует зависимость от длины строк, просто если игнорировать этот параметр то у обычного QS будет такая же оценка в среднем (n log n) и выигрыш не так очевиден.
По поводу «Преимущество над быстрой сортировкой в том, что нам не требуется сравнивать элементы «целиком»» так строки крайне редко полностью приходится сравнивать, до первого различия обычно.
По поводу «Преимущество над быстрой сортировкой в том, что нам не требуется сравнивать элементы «целиком»» так строки крайне редко полностью приходится сравнивать, до первого различия обычно.
Ну нас есть путь равенства первых символов.
Таким образом, мы «укорачиваем» строки, попавшие в данную часть на один символ — ведь мы и так знаем, что первый символ равен, его больше сравнивать не надо.
В обычном qsort пришлось бы каждый раз начинать с начала строки и бежать до первой разной буквы.
Т.к. массивы строк могут быть большими (по сравнению с размером алфавита), то на каждом шаге в раздел «одинаковые первые буквы» будет попадать достаточное количество строк, соответственно, мы неплохо сократим общее число операции сравнения букв.
Таким образом, мы «укорачиваем» строки, попавшие в данную часть на один символ — ведь мы и так знаем, что первый символ равен, его больше сравнивать не надо.
В обычном qsort пришлось бы каждый раз начинать с начала строки и бежать до первой разной буквы.
Т.к. массивы строк могут быть большими (по сравнению с размером алфавита), то на каждом шаге в раздел «одинаковые первые буквы» будет попадать достаточное количество строк, соответственно, мы неплохо сократим общее число операции сравнения букв.
Использовать radix, который требует дополнительную память, тоже не слишком мотивирует — строки могут быть большими
Насколько я понимаю, при реализации алгоритма дополнительная память будет расходоваться на хранение указателей на строки, а не на хранение дополнительных строковых данных. В этом случае длина строк никак не влияет на дополнительную память — строки могут быть как короткими, так и длинными, без разницы.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Трехпутевая поразрядная быстрая сортировка