Comments 24
Платный алгоритм сортировки? С учетом того, что сорцы доступны, я что-то сомневаюсь, что все, у кого есть этот алгоритм в программах платили за него деньги
Про сложность не уверен. Если у всех строк первые 10^7 символов совпадают, не придётся ли алгоритму проверить их все, прежде чем перейти собственно к сортировке? И не будет ли память для вспомогательных массивов зависеть ещё и от длины строк?
>>> Если у всех строк первые 10^7 символов совпадают, не придётся ли алгоритму проверить их все, прежде чем перейти собственно к сортировке?
Линн Д. Ярбро и так и сяк тестировал сортировку, о чём он более-менее подробно описал здесь.
Действительно, худшая временная сложность у сортировки O(n * k), где k — количество обрабатываемых разрядов. Как раз относится к предложенному Вами варианту.
Немного подкорректировал таблицу характеристик алгоритма, добавил худшую и лучшую временную сложность.
>>> И не будет ли память для вспомогательных массивов зависеть ещё и от длины строк?
Трекер слов (основной пожиратель дополнительной памяти) — точно не будет. Сортировка устроена так что при любых раскладах в качестве word tracker достаточно только одномерного массива из n элементов.
От длины строк прямо зависит трекер букв, но если сортировать список из миллиона элементов то его размерами можно пренебречь при оценке памяти.
Линн Д. Ярбро и так и сяк тестировал сортировку, о чём он более-менее подробно описал здесь.
Действительно, худшая временная сложность у сортировки O(n * k), где k — количество обрабатываемых разрядов. Как раз относится к предложенному Вами варианту.
Немного подкорректировал таблицу характеристик алгоритма, добавил худшую и лучшую временную сложность.
>>> И не будет ли память для вспомогательных массивов зависеть ещё и от длины строк?
Трекер слов (основной пожиратель дополнительной памяти) — точно не будет. Сортировка устроена так что при любых раскладах в качестве word tracker достаточно только одномерного массива из n элементов.
От длины строк прямо зависит трекер букв, но если сортировать список из миллиона элементов то его размерами можно пренебречь при оценке памяти.
Ну вот, лишили магистра богословия денег на постройку крайне важного храма.
Так это же сортировка при помощи trie, просто с оптимизированным представлением trie. Патент анулировать.
Казалось бы, это полностью эквивалентно поразрядной сортировке
Но ведь сортировка со средним временем работы O(n) невозможна, не так ли? Из статьи совсем непонятно, откуда взялась эта оценка именно для среднего (а не лучшего) случая.
Я с Вами соглашусь, средняя временная сложность O(n) — это последствия моего куцего перевода с английского.
Средняя временная сложность у этой сортировки — O(n * k), где k — количество обрабатываемых разрядов. Внёс изменения в статью, спасибо за замечание.
Средняя временная сложность у этой сортировки — O(n * k), где k — количество обрабатываемых разрядов. Внёс изменения в статью, спасибо за замечание.
Ну почему же невозможна? Например можно 32 разрядные числа сортировать за линейное время (в худшем случае), можно и 64 разрядные, и 128 разрядные и т.д…
Числа и строки подходят для блочной сортировки, которая может происходить за линейное время, так как их можно не только сравнивать, но и распределять по «корзинам».
Ограничивая диапазон значений — конечно можно. Но в общем массив чисел или строк сортировать за линейное время нельзя.
Я именно об этом и говорю. Для целых, например, ограничения на размер элемента достаточно чтобы отсортировать за линейное время. Также если строки ограничить по длине — то сортировку можно выполнять за линейное время.
Никто и не говорит что в общем случае можно, т.к. в общем случае только чтение будет зависеть не только от размера массива, но и от размера элементов в этом массиве.
Никто и не говорит что в общем случае можно, т.к. в общем случае только чтение будет зависеть не только от размера массива, но и от размера элементов в этом массиве.
Эта сортировка не со средним, а с худшим временем O(n*k). В случае строк получится даже O(V), где V — общий объём входных данных.
Фамилия создателя сортировки многое говорит о нем. =)
В РФ патенты на алгоритмы не имеют силы, так что автора можно смело игнорировать :)
Sign up to leave a comment.
ABC-сортировка