Здравствуйте, ylp, Вы писали:
ylp>Понятно, если вы предполчитаете не отвечать на прямо поставленые вопросы о том, что у вас за p в формуле оценки числа сравнений
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, white_znake, Вы писали:
_>>Ну как бы Radix Sort работает только для целых положительных чисел.
CM>Тут есть такой нюанс — на компьютере, абсолютно любые данные представляют собой набор байтов. То есть — положительных целых чисел. Странно, что так много программистов этого не понимают.
Да но, тут ньюанс в том, что строки бывают переменной длинны, алгоритм поразрядной сортировки дает сложность: O(k * n), где к — кол-во разрядов в сортируемых элементах, т.к. все сортируемые элементы должны иметь одинаковое кол-во разрядов, то получается, что к — константа, поэтому сложность O(n).
Если же применить алгоритм поразрядной сортировки к строкам переменной длинны, то получается, что перед самой сортировкой, строки надо будет выровнять, но само выравнивание сложнее чем O(n) ("решение в лоб" — O(n*n)). Поэтому алгоритм поразрядной сортировки для строк переменной длинны будет иметь сложность > O(n).
В тоже время quick sort отсортирует и строки переменной длинны и числа — за то же самое O(n * log n).
Здравствуйте, CoderMonkey, Вы писали:
CM>Здравствуйте, Zhendos, Вы писали:
> И вместо C1 * O(N) ты получишь C2 * O(N), где C2 < C1 Z>>Поэтому операция умножения O(N) на константу очень странно выглядит.
CM>Нет, не выглядит. Читать учебники.
Учебники это комиксы про программистов или может быть твитер какого-то XYZ?
Здравствуйте, white_znake, Вы писали:
_>т.к. все сортируемые элементы должны иметь одинаковое кол-во разрядов
Нет, не должны.
_>Если же применить алгоритм поразрядной сортировки к строкам переменной длинны, то получается, что перед самой сортировкой, строки надо будет выровнять
Нет, не нужно.
_>В тоже время quick sort отсортирует и строки переменной длинны и числа — за то же самое O(n * log n).
А ты думаешь, что сравнение строк большой длины в квиксорте магическим образом будет таким же быстрым, как и коротких?
Здравствуйте, Zhendos, Вы писали:
Z>Учебники это комиксы про программистов или может быть твитер какого-то XYZ?
Учебники — это любые учебники. Только надо не только читать, а еще и понимать смысл.
Z>"И вместо O(N) ты получишь O(N)", Z>что для меня звучит бредово
Это очень плохо, что для тебя это так звучит. Как бы намекает на уровень понимания. Потому что алгоритмы с формально одинаковым O(N) запросто могут различаться на порядки по реальной производительности.
Просвещайся: http://pages.cs.wisc.edu/~vernon/cs367/notes/3.COMPLEXITY.html#constants
Здравствуйте, CoderMonkey, Вы писали:
BFE>>Что это значит?
CM>Простой способ "что делать, если строка короче остальных". CM>Уточняющий вопрос — ты уверен, что вообще понимаешь, как работает алгоритм?
Нет, я не понимаю, как работает алгоритм.
Я правильно понимаю, что если строка короче какой-то другой строки, то мы используем специальный бакет. Бакет — это корзина. Так?
Здравствуйте, B0FEE664, Вы писали:
BFE>Нет, я не понимаю, как работает алгоритм. BFE>Я правильно понимаю, что если строка короче какой-то другой строки, то мы используем специальный бакет. Бакет — это корзина. Так?
У нас есть набор строк разной длины в случайном порядке.
1. Сначала смотрим по первому символу и раскидываем строки по корзинам, в каждой корзине — все строки начинаются на один тот же символ. (это на самом деле скорее Bucket sort и этот вариант сравнительно неэффективен, но зато он самый простой для понимания).
2. Если в корзине <=1 символа, то делать с ней больше ничего не нужно.
3. Если >1, то проделываем со строками в корзине рекурсивно ту же операцию, но уже по второму символу в строке, и распределяем их по под-корзинам. И так далее.
Как нетрудно сообразить, операция распределения по под-корзинам продожается, только пока в текущей корзине есть строки с одинаковыми префиксами. Как только у строк разные символы в текущей позиции — всё, стоп, дальше делать ничего не нужно.
И собственно ответ на твой вопрос "зачем специальный бакет".
abc
abdef
abcxy
В этом случае, когда мы доходим до символа с i=3, нужен специальный бакет для строки abc, поскольку никакого символа в этой позиции там уже нет.
Здравствуйте, CoderMonkey, Вы писали:
CM>У нас есть набор строк разной длины в случайном порядке. CM>1. Сначала смотрим по первому символу и раскидываем строки по корзинам, в каждой корзине — все строки начинаются на один тот же символ. (это на самом деле скорее Bucket sort и этот вариант сравнительно неэффективен, но зато он самый простой для понимания). CM>2. Если в корзине <=1 символа, то делать с ней больше ничего не нужно. CM>3. Если >1, то проделываем со строками в корзине рекурсивно ту же операцию, но уже по второму символу в строке, и распределяем их по под-корзинам. И так далее. CM>Как нетрудно сообразить, операция распределения по под-корзинам продожается, только пока в текущей корзине есть строки с одинаковыми префиксами. Как только у строк разные символы в текущей позиции — всё, стоп, дальше делать ничего не нужно.
Здравствуйте, B0FEE664, Вы писали:
BFE>Это блочная сортировка, а не Radix Sort.
Разница между ними — чисто косметическая. В случае с MSD radix, практически вся разница — что нужно не раскладывать по корзинам, а считать элементы в них, и раскладывать уже потом
Хотя, есть много разных вариантов.
Здравствуйте, CoderMonkey, Вы писали:
BFE>>Это блочная сортировка, а не Radix Sort. CM>Разница между ними — чисто косметическая. В случае с MSD radix, практически вся разница — что нужно не раскладывать по корзинам, а считать элементы в них, и раскладывать уже потом
Нет, насколько я понимаю. Для Radix Sort надо начинать с последнего символа строки, а не с первого.
CM>Хотя, есть много разных вариантов.
И все они называются по разному.
