Я с Вами соглашусь, средняя временная сложность O(n) — это последствия моего куцего перевода с английского.
Средняя временная сложность у этой сортировки — O(n * k), где k — количество обрабатываемых разрядов. Внёс изменения в статью, спасибо за замечание.
>>> Если у всех строк первые 10^7 символов совпадают, не придётся ли алгоритму проверить их все, прежде чем перейти собственно к сортировке?
Линн Д. Ярбро и так и сяк тестировал сортировку, о чём он более-менее подробно описал здесь.
Действительно, худшая временная сложность у сортировки O(n * k), где k — количество обрабатываемых разрядов. Как раз относится к предложенному Вами варианту.
Немного подкорректировал таблицу характеристик алгоритма, добавил худшую и лучшую временную сложность.
>>> И не будет ли память для вспомогательных массивов зависеть ещё и от длины строк?
Трекер слов (основной пожиратель дополнительной памяти) — точно не будет. Сортировка устроена так что при любых раскладах в качестве word tracker достаточно только одномерного массива из n элементов.
От длины строк прямо зависит трекер букв, но если сортировать список из миллиона элементов то его размерами можно пренебречь при оценке памяти.
Я уже вижу по минусам в карму, что мой грех неискупим. Осталось только понять что именно навлекло на меня гнев хабражителей. Также мне теперь не даёт покоя вопрос кто такой Паоло.
Я Вам поставил в карму плюс, за дневник ничего не ставил.
Для человека, который пытается выбраться из хабраямы, плюса в общем-то не жалко.
Но если честно, надоели бесполезные дневники, которые постоянно используются для «recovery mode» (с тематикой «Ой, глядите — позавчера/вчера/сегодня известная компания *** обоср-сь!»). Если хотите чтобы Вас с радостью приняли обратно в ряды — напишите что-то, что будет актуальным дольше чем пару часов.
Распределительные сортировки (подсчётом, поразрядная, блочная) не используют сравнения элементов массива между собой и ключи поэтому не сохраняются. Эти сортировки классифицируют элементы по общим признакам.
Они обычно работают быстрее чем известные эффективные сортировки других видов (quick sort, merge sort, heap sort и кое-какие другие) но Вы точно заметили их существенный недостаток: ограниченная применимость (обычно заточены под целые числа или строки).
Быстрая сортировка работает очень быстро и она универсальна. Поэтому она так популярна и широко используема. Но для каких-то узких специфических задач другие сортировки могут работать намного быстрее.
Хороший метод. Показывает, видит ли кандидат конретные ляпы и насколько умеет ухватывать общее назначение кода, дабы подмечать где «неочевидная бизнес-логика», а где «бесполезная информация в логах».
Если шустро щёлкает первое — можно смело брать джуниором или даже миддлом (по итогам дальнейшего общения), если глобально оценивает код — значит повезло, перед Вами потенциальный senior.
>>> Не понятно, как в такой сортировке данные к ключу привязывать?
В статье в двух местах приведена ссылка на реализацию сортировки на 37 языках программирования.
>>> Т.е. например отсортировать строки в таблице по натуральному ключу?
Алгоритм использует свойства натуральных чисел и поэтому «заточен» прежде всего под упорядочивание целых чисел больше нуля.
Сортировать бисером можно и что-то другое, строки в том числе (можно придумать какие-то способы приведения строку в целое число и обратно), но это уже извращение. Сортировка изначально придумана под натуральные числа.
>>> А если ни как, то какой хоть один параметр у нее лучше чем у Сортировки подсчетом?
Сортировка подсчётом во всех отношениях намного эффективнее чем бисерная сортировка. Более того — бисерная сортировка это разновидность сортировки подсчётом, причём разновидность весьма медленная и крайне расточительно использующая память.
Зачем вообще нужна тогда Bead sort и на кой чёрт о ней писать целую статью? Прежде всего научный интерес: в целях образования, для любителей поразбирать алгоритмы. Неэффективные методы также полезно изучать как и эффективные. Да и на практике вдруг кому-то пригодится — приём тотального сдвига может понадобиться для решения какой-нибудь задачи, вообще не связанной с сортировкой.
>>> Вы забыли, что шарики следует сначала разместить (по-одному), а потом еще и подсчитать обратно.
Для временной сложности алгоритма не играет роли всякого рода подготовительные мероприятия. Вы ж не подсчитываете время, которое Вам нужно на то, чтобы набрать программу с помощью клавиатуры.
>>> Ни один алгоритм не может выполнить меньше операций, чем объем требуемой для него памяти.
Бисерная сортировка примечательна тем, что её часто рассматривают не как алгоритм/программу, а как некое физическое устройство с шариками на спицах или электрическую цепь из резисторов. Речь о памяти в этом случае просто не идёт.
Я ж, надеюсь, вы не слово bitch имели в виду. :)
Средняя временная сложность у этой сортировки — O(n * k), где k — количество обрабатываемых разрядов. Внёс изменения в статью, спасибо за замечание.
В классической radix sort просматриваются все разряды. В ABC-сортировке перебор разрядов прекращается как только список упорядочен.
Линн Д. Ярбро и так и сяк тестировал сортировку, о чём он более-менее подробно описал здесь.
Действительно, худшая временная сложность у сортировки O(n * k), где k — количество обрабатываемых разрядов. Как раз относится к предложенному Вами варианту.
Немного подкорректировал таблицу характеристик алгоритма, добавил худшую и лучшую временную сложность.
>>> И не будет ли память для вспомогательных массивов зависеть ещё и от длины строк?
Трекер слов (основной пожиратель дополнительной памяти) — точно не будет. Сортировка устроена так что при любых раскладах в качестве word tracker достаточно только одномерного массива из n элементов.
От длины строк прямо зависит трекер букв, но если сортировать список из миллиона элементов то его размерами можно пренебречь при оценке памяти.
Для человека, который пытается выбраться из хабраямы, плюса в общем-то не жалко.
Но если честно, надоели бесполезные дневники, которые постоянно используются для «recovery mode» (с тематикой «Ой, глядите — позавчера/вчера/сегодня известная компания *** обоср-сь!»). Если хотите чтобы Вас с радостью приняли обратно в ряды — напишите что-то, что будет актуальным дольше чем пару часов.
Сортировки обменами
Сортировки вставками
Сортировки выбором
Сортировки слиянием
Сортировки распределением
Гибридные сортировки
Параллельные сортировки
Быстрая относится к обменным.
Распределительные сортировки (подсчётом, поразрядная, блочная) не используют сравнения элементов массива между собой и ключи поэтому не сохраняются. Эти сортировки классифицируют элементы по общим признакам.
Они обычно работают быстрее чем известные эффективные сортировки других видов (quick sort, merge sort, heap sort и кое-какие другие) но Вы точно заметили их существенный недостаток: ограниченная применимость (обычно заточены под целые числа или строки).
Быстрая сортировка работает очень быстро и она универсальна. Поэтому она так популярна и широко используема. Но для каких-то узких специфических задач другие сортировки могут работать намного быстрее.
Если шустро щёлкает первое — можно смело брать джуниором или даже миддлом (по итогам дальнейшего общения), если глобально оценивает код — значит повезло, перед Вами потенциальный senior.
В статье в двух местах приведена ссылка на реализацию сортировки на 37 языках программирования.
>>> Т.е. например отсортировать строки в таблице по натуральному ключу?
Алгоритм использует свойства натуральных чисел и поэтому «заточен» прежде всего под упорядочивание целых чисел больше нуля.
Сортировать бисером можно и что-то другое, строки в том числе (можно придумать какие-то способы приведения строку в целое число и обратно), но это уже извращение. Сортировка изначально придумана под натуральные числа.
>>> А если ни как, то какой хоть один параметр у нее лучше чем у Сортировки подсчетом?
Сортировка подсчётом во всех отношениях намного эффективнее чем бисерная сортировка. Более того — бисерная сортировка это разновидность сортировки подсчётом, причём разновидность весьма медленная и крайне расточительно использующая память.
Зачем вообще нужна тогда Bead sort и на кой чёрт о ней писать целую статью? Прежде всего научный интерес: в целях образования, для любителей поразбирать алгоритмы. Неэффективные методы также полезно изучать как и эффективные. Да и на практике вдруг кому-то пригодится — приём тотального сдвига может понадобиться для решения какой-нибудь задачи, вообще не связанной с сортировкой.
Мы же их на единицы раскладываем. Тогда понадобится. )
Если мы увеличим каждое число в 10 раз, всё-таки памяти в 10 раз больше не понадобится.
Для временной сложности алгоритма не играет роли всякого рода подготовительные мероприятия. Вы ж не подсчитываете время, которое Вам нужно на то, чтобы набрать программу с помощью клавиатуры.
>>> Ни один алгоритм не может выполнить меньше операций, чем объем требуемой для него памяти.
Бисерная сортировка примечательна тем, что её часто рассматривают не как алгоритм/программу, а как некое физическое устройство с шариками на спицах или электрическую цепь из резисторов. Речь о памяти в этом случае просто не идёт.