Какова самая неэффективная процедура сортировки?

Question

Для массива целых чисел, какой наименее эффективный способ сортировки массива.Функция должна прогрессировать на каждом этапе (например, без бесконечного цикла).Какова продолжительность выполнения этого алгоритма?

Answer 1

Не может быть ни одного эффективного алгоритма для чего-либо.Это может быть легко доказано противоречием, если принять, что, исходя из любого алгоритма, можно построить другой эквивалентный, но менее эффективный алгоритм.

Answer 2

Bogosort имеет среднее время выполнения O(n*n!), ой.

Answer 3

глупая сортировка , безусловно, худший алгоритм.Это не совсем бесконечный цикл, но этот подход имеет наихудший случай O(inf), а среднее значение равно O(n × n!).

Answer 4

Вы можете сделать это в O(n!*n), сгенерировав все уникальные перестановки и затем проверив, отсортирован ли массив.

Answer 5

Наименее эффективным алгоритмом, который я могу представить с конечной верхней границей времени выполнения, является сортировка перестановок.Идея состоит в том, чтобы генерировать каждую перестановку (комбинацию) входных данных и проверять, отсортирована ли она.

Верхняя граница O (n!), Нижняя граница O (n), когда массив уже отсортирован.

Answer 6

1. Выполните итерацию по всем конечным последовательностям целых чисел, используя диагонализацию.
2. Для каждой последовательности проверьте, отсортирована ли она.
3. Если это так, проверьте, соответствуют ли ее элементы элементам в вашем массиве.

Это будет иметь верхнюю границу (первое предположение: O (n ^ (n * m)?).

Answer 7

"Worstsort" имеет сложность , где факториал из n повторенных m раз.Бумагу Мигеля А. Лермы можно найти здесь .

Answer 8

Bogosort - худший алгоритм сортировки, использующий перемешивание.Но, с другой стороны, вероятность сортировки массива за один шаг мала:)

Answer 9

Странный вопрос, обычно мы идем к самому быстрому.

Найдите самое высокое и переместите его в список.Повторяйте предыдущий шаг, пока в исходном списке не останется только один элемент.Вам гарантировано O (N ^ 2).