Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 54
А что насчёт Sleep Sort?
Я так понимаю сложность O(n)
O(max-value + n)
Если max-value — константа, то то что вы написали равно O(n).
О() определяет то, как увеличится нужное кол-во операций при увеличении числа сортируемых элементов.
О() определяет то, как увеличится нужное кол-во операций при увеличении числа сортируемых элементов.
O(C) = 0 так как изменение числа элементов не влияет на результат (например время обращения к элементу массива по индексу не зависит от размера массива)O(C+N)=O(C)+O(N) = O(N)max-value — максимальное значение элемента. И это не константа. И да, я знаю что такое O-большое.
Все-таки max-value не константа, это максимальное значение во входном массиве. И от него действительно зависит время выполнения алгоритма. Для примера, что рост времени выполнения алгоритма нелинеен от n, можно рассмотреть массивы {1, 9999999999999999} и {1, 2, 3, ..., 1000, 9999999999999999}. Оба массива будут сортированы за одинаковое время (если не учитывать время на инициализацию потоков).
Так что приведенная выше формула верна, O(m + n).
Так что приведенная выше формула верна, O(m + n).
1) А если n константа, то вообще O(1).
2) Если max-value константа, то O(max-value + n) = O(n)
Так что странное возражение.
2) Если max-value константа, то O(max-value + n) = O(n)
Так что странное возражение.
Серьёзно? ЗаO(C) = 0так как изменение числа элементов не влияет на результат (например время обращения к элементу массива по индексу не зависит от размера массива)
O(C+N)=O(C)+O(N) = O(N)
O(C) = 0 вообще по рукам бить надо.O(C) = O(1)C + n = O(n)SleepSort не зависит от N. Время работы алгоритма константное. Зависит от максимального размера сортируемых чисел и времени задержки.
А как же затраты на создание процессов?
Речь идет об алгоритмической сложности. Ей чужды такие низменные вещи, как процессор, память, диск…
А вот и нет, эта операция, сколь бы мало времени она не занимала в асимптотической оценке должна участвовать. При достаточно больших n, и малых значениях чисел, время работы будет вести себя линейно по n.
Не могу смотреть на такую несправедливость, так что поддержу.
В SleepSort всё равно нужно из главного потока создать N вспомогательных, ну или, если переиспользовать вспомогательные потоки, как ниже предлагают, то N раз передать информацию о наличии числа в нужный поток.
Следовательно даже если пренебречь временем работы шедьюлера ОС, мы должны сделать минимум N операций в основном потоке.
Интересен тот факт, что если мы задумаемся как мог бы быть реализован шедьюлер (очередь с приоритетами = куча например), то получим O(ln(N)) на вставку, и общее время работы сортировки в привычные O(N ln(N))
В SleepSort всё равно нужно из главного потока создать N вспомогательных, ну или, если переиспользовать вспомогательные потоки, как ниже предлагают, то N раз передать информацию о наличии числа в нужный поток.
Следовательно даже если пренебречь временем работы шедьюлера ОС, мы должны сделать минимум N операций в основном потоке.
Интересен тот факт, что если мы задумаемся как мог бы быть реализован шедьюлер (очередь с приоритетами = куча например), то получим O(ln(N)) на вставку, и общее время работы сортировки в привычные O(N ln(N))
Можно заранее создать тредпул с количеством тредов равным максимальному размеру сортируемых чисел. Время его создания будет константным и не зависит от числа сортируемых элементов.
В некотором смысле SleepSort это временнОе представление radix sort. Только вместо индекса в массиве у вас секунды.
Только не radix sort, а сортировка подсчетом. И у нее сложность будет именно O(n+k): википедия
Время работы алгоритма константное
Очевидно, что это не так. Доказательство — наличие цикла while с количеством итераций равным количеству элементов.
Да. Согласен. Количество сортируемых элементов может быть любым. А значит время запуска алгоритма не ограничено и линейно растет с числом элементов.
Спасибо.
Спасибо.
Да, видимо в этом и есть причина спора. Считать ли операцию запуска алгоритма частью алгоритма?
Если да, то линейное. Если нет — константа.
Если да, то линейное. Если нет — константа.
Дело не только в запуске. Потоки не завершают свое выполнение мгновенно, и Sleep не занимает строго заданное количество времени.
Например, сортировка массива из 10 одинаковых элементов и 1000 одинаковых элементов с теми же значениями займет разное время. Хотя в этом случае зависимость вряд ли будет линейной.
Например, сортировка массива из 10 одинаковых элементов и 1000 одинаковых элементов с теми же значениями займет разное время. Хотя в этом случае зависимость вряд ли будет линейной.
Так зависит все от планировщика ОС. Он собственно и занимается сортировкой, решая, какой процесс пора пробудить. Может он в очередь с приоритетом их выстраивает, тогда это будет по сути heapsort.
Получалась слишком долгая анимация, пришлось отказаться )))
А как же StackSort?
Бабушкин рулит — все-таки наш человек. :)))
Вот вы смеетесь, а вычислиние числа Бабушкина весьма тривиальная задача.
Решение
Для этого я предлагаю использовать дополнительный, третий массив. Отсортируем 1-й массив QuickSort-ом, например. Результат запишем в 3-й массив. Далее, мы можем построить таблицу соответствия, из которой мы и получаем число Бабушкина.
Пример:
Массив-1:
Массив-3 (уже заполненный):
Таблица соответствия:
(поскольку один разряд указывает на один элемент массива, при формировании таблицы индексы необходимо перевести в систему счисления с основанием n, где n — длина сортируемого массива)
Несложно заметить, что числом Бабушкина является 2-й столбец (при чтении сверху вниз). Запишем его:
(не забываем, что число у нас в четверичной системе счисления)
Для вычисления чисел, при делении которых, дробная часть равна числу Бабушкина, нам необходимо вычислить логарифм этого числа по основанию n, где n — длинна массива (d). Теперь, если возвести n в степень d+1, получим делитель. Число Бабушкина же будет делимым.
Все, можно приступать к сортировке Бабушкина.
Пример:
Массив-1:
3 1 2 5
Массив-3 (уже заполненный):
1 2 3 5
Таблица соответствия:
[0] > [2]
[1] > [0]
[2] > [1]
[3] > [3]
(поскольку один разряд указывает на один элемент массива, при формировании таблицы индексы необходимо перевести в систему счисления с основанием n, где n — длина сортируемого массива)
Несложно заметить, что числом Бабушкина является 2-й столбец (при чтении сверху вниз). Запишем его:
2013
(не забываем, что число у нас в четверичной системе счисления)
Для вычисления чисел, при делении которых, дробная часть равна числу Бабушкина, нам необходимо вычислить логарифм этого числа по основанию n, где n — длинна массива (d). Теперь, если возвести n в степень d+1, получим делитель. Число Бабушкина же будет делимым.
Все, можно приступать к сортировке Бабушкина.
Есть ещё вариант вычислить число Бабушкина — надо позвонить Бабушкину по телефону и спросить это число.
По своему опыту скажу, что лучше всего звонить поздно ночью, тогда шанс что Бабушкин будет занят чем-то другим очень низок и это будет сильно способствовать увеличению общей производительности алгоритма.
По своему опыту скажу, что лучше всего звонить поздно ночью, тогда шанс что Бабушкин будет занят чем-то другим очень низок и это будет сильно способствовать увеличению общей производительности алгоритма.
«Иммунитет» хорошо проявляет себя в паре с другим антивирусом. (Бабушкин)
Сортировка Бабушкина особенно эффективна в симбиозе с другой сортировкой.
Сортировка Бабушкина особенно эффективна в симбиозе с другой сортировкой.
А как же Quantum Bogosort?!
Алгоритм, в котором предполагается, что теория о множестве вселенных верна. Тогда алгоритм получается следующий:
1. Проверить отсортирован ли массив?
2. Если нет, уничтожить вселенную.
В конце останется лишь вселенная, в которой массив изначально был отсортирован.
Мой любимый.
Алгоритм, в котором предполагается, что теория о множестве вселенных верна. Тогда алгоритм получается следующий:
1. Проверить отсортирован ли массив?
2. Если нет, уничтожить вселенную.
В конце останется лишь вселенная, в которой массив изначально был отсортирован.
Мой любимый.
Просто это работает только на тех платформах, где присутствует инструкция «уничтожить Вселенную».
А вообще, перевели бы www.reddit.com/r/programming/comments/thtx/my_new_favorite_sorting_algorithm/
> Клоун Бозо™ сортирует со средней временной сложностью O(n x n!) и это же является и верхней границей по времени.
Как такое может быть? Ведь в худшем случае мы будем постоянно переставлять одни и те же два элемента, так что верхняя граница — бесконечность. Или вы как-то по другому определяете верхнюю границу для рандомизированных алгоритмов? Верхняя граница только по входным данным, с усреднением по выдаче ГПСЧ?
Как такое может быть? Ведь в худшем случае мы будем постоянно переставлять одни и те же два элемента, так что верхняя граница — бесконечность. Или вы как-то по другому определяете верхнюю границу для рандомизированных алгоритмов? Верхняя граница только по входным данным, с усреднением по выдаче ГПСЧ?
Кстати зря смеётесь над алгоритмом Бабушкина: как ни странно он даёт вполне пристойную сортировку.
Алгоритм: строим цепную дробь для числа Бабушкина. В какой-то момент либо цепная дробь закончится (т.к. конечна), либо ошибка будет меньше последнего разряда (и поскольку отклонение приближения цепными дробями на каждом шаге меняет знак, эта либо следующая дробь подойдёт под условие «совпадает с точностью до последнего знака»). Каждый шаг цепной дроби сводится к обращению длинного числа (разделить 1 на него).
Рост знаменателя приближения цепной дробью, насколько я помню, оценивается как y^k, где k — количество шагов, y — константа. При этом отклонение от искомого числа Бабушкина не больше 1/(квадрат знаменателя).
Сложение-вычитания длинных чисел — линейны, количество шагов — логарифм. Таким образом, оценка скорости поиска пары чисел для числа Бабушкина: O(сложность деления длинных чисел * logn). Сложность деления 1 на длинное число по этой статье сводится к сложности умножения
citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.7394&rep=rep1&type=pdf
т.е. O(n * logn).
Таким образом, алгоритм будет работать за O(n*log^2(n)) — что весьма неплохо.
Алгоритм: строим цепную дробь для числа Бабушкина. В какой-то момент либо цепная дробь закончится (т.к. конечна), либо ошибка будет меньше последнего разряда (и поскольку отклонение приближения цепными дробями на каждом шаге меняет знак, эта либо следующая дробь подойдёт под условие «совпадает с точностью до последнего знака»). Каждый шаг цепной дроби сводится к обращению длинного числа (разделить 1 на него).
Рост знаменателя приближения цепной дробью, насколько я помню, оценивается как y^k, где k — количество шагов, y — константа. При этом отклонение от искомого числа Бабушкина не больше 1/(квадрат знаменателя).
Сложение-вычитания длинных чисел — линейны, количество шагов — логарифм. Таким образом, оценка скорости поиска пары чисел для числа Бабушкина: O(сложность деления длинных чисел * logn). Сложность деления 1 на длинное число по этой статье сводится к сложности умножения
citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.71.7394&rep=rep1&type=pdf
т.е. O(n * logn).
Таким образом, алгоритм будет работать за O(n*log^2(n)) — что весьма неплохо.
Когда в детстве только знакомился с программированием, довольно быстро придумал свой алгоритм сортировки. Создаем второй массив такого же размера. Обходим исходный массив в поиске наименьшего элемента. Записываем в новый. Снова обходим первый массив в поиске наименьшего но большего чем предыдущий и т.д. Сложность очевидно O(n x n). Причем стабильно при любом раскладе.
О каноничных алгоритмах сортировки узнал почему-то только в универе.
PS: сейчас подумал, что в алгоритме очевидный баг: если в исходном массиве есть одинаковые элементы, то в результирующем они будут в единственном экземпляре.
О каноничных алгоритмах сортировки узнал почему-то только в универе.
PS: сейчас подумал, что в алгоритме очевидный баг: если в исходном массиве есть одинаковые элементы, то в результирующем они будут в единственном экземпляре.
Может вы не в курсе, но ваш алгоритм — самая что ни на есть каноничная «сортировка выбором», о которой написано даже на википедии
Ну, «изобрести» в детстве то что уже давно придумано — это святое. Если в юном возрасте есть желание и попытки «вносить свой вклад в науку» то можно только поприветствовать. Лишь бы в дальнейшем это не приобретало клинических форм как у некоторых.
Кроме того, приведённый способ не является «самой что ни на есть каноничной «сортировкой выбором». Об этом свидетельствует и честно признаваемая автором применимость только к массивам с неповторяющимися элементами. А также использование дополнительного массива (в классической selection sort расходов на дополнительную память нет).
Кроме того, приведённый способ не является «самой что ни на есть каноничной «сортировкой выбором». Об этом свидетельствует и честно признаваемая автором применимость только к массивам с неповторяющимися элементами. А также использование дополнительного массива (в классической selection sort расходов на дополнительную память нет).
Бабушкин опять на пике популярности. Я все жду, когда он изобретет свои структуры данных типа «деревьев Бабушкина». Так же очень жду открытий в теории графов — «граф Бабушкина», «критерий Бабушкинности графа» и т.д…
Добавлю аналог Bogo: сортировка болотным пузырьком.
Если упрощённо, то:
function BogoSort2(array){
array.sort(function(){ return Math.random() > 0.5; });
if( !isSorted(array) ) return BogoSort2(array);
return array;
}
function isSorted(array){
for(var i = 1, l = array.length; i < l; i++){
if(array[i] < array[i-1]) return false;
}
return true;
}
// заранее хочу извиниться за то, что 1. саму сортировку пузырьком лень писать, тем более, что во многих языках она есть. 2. не на Java, как в посте, а на JS. 3. отсутствие тега source, карма не позволяет.
Если упрощённо, то:
function BogoSort2(array){
array.sort(function(){ return Math.random() > 0.5; });
if( !isSorted(array) ) return BogoSort2(array);
return array;
}
function isSorted(array){
for(var i = 1, l = array.length; i < l; i++){
if(array[i] < array[i-1]) return false;
}
return true;
}
// заранее хочу извиниться за то, что 1. саму сортировку пузырьком лень писать, тем более, что во многих языках она есть. 2. не на Java, как в посте, а на JS. 3. отсутствие тега source, карма не позволяет.
Для заинтересовавшихся оформлю в более наглядном виде:
function BogoSort2(array) {
array.sort(function() {
return Math.random() > 0.5;
});
if (!isSorted(array)) return BogoSort2(array);
return array;
}
function isSorted(array) {
for(var i = 1, l = array.length; i < l; i++) {
if(array[i] < array[i-1]) return false;
}
return true;
}
По этому поводу был даже выпуск xkcd http://xkcd.com/1185/
А знаю еще более худший и варварский способ!
Называется — генетический алгоритм :-)
Берем начальный массив, массив генома — порядок расположения элементов в сортированном массиве.
А дальше тупо перебираем ВСЕ геномы и постоянно сохраняем лучший.
Можно оптимизировать, но тогда упадет временная сложность :-)
Итак, все то же, но по шагам:
1)задаем массив последовательными значениям от 1 до n. Говорим, что он лучший
2)проходимся по orig[genom[i]] и проверяем на неубываемость
3)сверяем количество неубывающих элементов текущего массива с количеством неубывающих элементов лучшего массива. Если текущий массив лучше лучшего, то он становится лучшим :-)
4)Если можем, формируем новую последовательность(перебором) и идем на шаг 2. Если не можем, выходим.
5) формируем итоговый массив.
Итоговая сложность — n*(2n+2)
Называется — генетический алгоритм :-)
Берем начальный массив, массив генома — порядок расположения элементов в сортированном массиве.
А дальше тупо перебираем ВСЕ геномы и постоянно сохраняем лучший.
Можно оптимизировать, но тогда упадет временная сложность :-)
Итак, все то же, но по шагам:
1)задаем массив последовательными значениям от 1 до n. Говорим, что он лучший
2)проходимся по orig[genom[i]] и проверяем на неубываемость
3)сверяем количество неубывающих элементов текущего массива с количеством неубывающих элементов лучшего массива. Если текущий массив лучше лучшего, то он становится лучшим :-)
4)Если можем, формируем новую последовательность(перебором) и идем на шаг 2. Если не можем, выходим.
5) формируем итоговый массив.
Итоговая сложность — n*(2n+2)
Также отмечу, что тем не менее BozoSort в среднем всё равно будет сортировать быстрее чем BogoSort. Просто потому, что после каждого обмена массив проверяется на упорядоченность. В BogoSort часты случаи, когда массив находится в упорядоченном состоянии, однако если в этот момент не произвести проверку, а перемешивать далее, то вожделенное состояние осортированности на время утрачивается.
Что за бред? Сам процесс проверки массива на упорядоченность слишком медленный. Поэтому BozoSort работает медленнее, просто за счет более частых проверок.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Непрактичные сортировки – бессмысленные и беспощадные