Есть ли какие-либо худшие алгоритмы сортировки, чем Сортировка по неразумному алгоритму (иначе Вид Обезьяны)? [закрытый]

Нет ничего хуже бесконечности.

Если вы сохраните смысл алгоритма каким-либо образом, O (n!) будет худшей верхней границей, которую вы можете достичь.

Так как проверка каждой возможности перестановки сортируемого набора потребует n! шагов, хуже некуда.

Если вы делаете больше шагов, то алгоритм не имеет реальной полезной цели. Не говоря уже о следующем простом алгоритме сортировки с O (бесконечность) :

list = someList
while (list not sorted):
    doNothing

В худшем случае производительность O (∞) может даже не сделать его алгоритмом согласно some .

Алгоритм - это просто последовательность шагов, и вы всегда можете сделать хуже, немного подправив его, чтобы получить желаемый результат за большее количество шагов, чем было раньше. Можно было намеренно ввести информацию о количестве шагов, сделанных в алгоритм, и заставить его завершить работу и выдать правильный результат только после того, как будет выполнено X количество шагов. Этот X вполне может иметь порядок O (n ² ) или O (n ^n! ) или что угодно, что алгоритм хотел бы сделать. Это эффективно увеличило бы как лучшие, так и средние границы случаев.

Но ваш худший сценарий невозможно превзойти :)

Quantum Bogosort

Алгоритм сортировки, который предполагает, что многомировая интерпретация квантовой механики верна:

1. Убедитесь, что список отсортирован. Если нет, уничтожьте вселенную.

По завершении алгоритма список будет отсортирован в единственной оставшейся вселенной. Этот алгоритм занимает время O (N) в худшем случае и время в среднем O (1). Фактически, среднее количество выполненных сравнений равно 2: существует 50% -ная вероятность того, что вселенная будет разрушена на втором элементе, 25% -ная вероятность, что она будет разрушена на третьем, и так далее.

Вам следует провести некоторое исследование в захватывающей области Pessimal Algorithms and Simplexity Analysis. Эти авторы работают над проблемой разработки сортировки с пессимальным лучшим случаем (лучший случай вашего bogosort'а равен Omega(n), а slowsort (см. статью) имеет неполиномиальную временную сложность лучшего случая).

Сортировка Бозо - это родственный алгоритм, который проверяет, отсортирован ли список, и, если нет, меняет два элемента местами. Он имеет одинаковые показатели в лучшем и худшем случае, но я интуитивно ожидаю, что средний случай будет длиннее, чем у Bogosort. Трудно найти (или получить) какие-либо данные о производительности этого алгоритма.

Вы можете замедлить работу любого алгоритма сортировки, выполняя шаг «Сортировано ли» случайным образом. Примерно так:

1. Создайте массив логических значений того же размера, что и массив, который вы сортируете. Установите для них все значение false.
2. Запустите итерацию bogosort.
3. Выберите два случайных элемента.
4. Если два элемента отсортированы относительно друг друга (i
5. Проверить, истинны ли все логические значения в массиве. Если нет, вернитесь к 3.
6. Готово.

1 Поместите свои вещи для сортировки на учетные карточки
2 Подбросьте их в ветреный день в миле от вашего дома .
2 Бросьте их в костер и убедитесь, что они полностью уничтожены.
3 Проверьте правильность расположения пола на кухне.
4 Повторите, если это неправильный порядок.

Лучший вариант сценария - O (∞)

Правка выше на основе проницательных наблюдений Кенни ™.

У меня был лектор, который однажды предложил создать случайный массив, проверить, отсортирован ли он, а затем проверить, совпадают ли данные с массивом, который нужно отсортировать.

В лучшем случае O (N) (первый раз, детка!) В худшем случае O (Никогда)

Да, SimpleSort, теоретически он работает в O(-1), однако это эквивалентно O(...9999) , что, в свою очередь, эквивалентно O(∞ - 1), что также эквивалентно O(∞). Вот мой пример реализации:

/* element sizes are uneeded, they are assumed */
void
simplesort (const void* begin, const void* end)
{
  for (;;);
}