Bogosort
Мы уже не раз работали с отсортированными списками в самых разных задачах. Часто мы пользуемся встроенными функциями для сортировки массивов. Однако не всегда понятно, как именно эти встроенные функции работают «под капотом». В этой главе мы рассмотрим некоторые из наиболее популярных алгоритмов сортировки, которые применяются в самых разных сценариях — в зависимости от задачи.
Первый алгоритм, о котором мы поговорим, — это самый абсурдный из всех алгоритмов сортировки. Он называется Bogosort. В реальных приложениях его нигде не используют, и вы вскоре поймёте, почему.
Имея
n чисел, алгоритм просто случайно перемешивает эти числа, а затем проверяет, отсортирован ли получившийся список:from random import shuffle
a = [3, 1, -2, 5, 6] # Исходные числа
while True: # Цикл, пока массив не будет отсортирован
is_sorted = True
for i in range(1, len(a)): # Цикл для проверки, отсортирован ли массив
if a[i] < a[i-1]: # Если находим элемент, который меньше предыдущего => массив не отсортирован
is_sorted = False # Устанавливаем переменную в False и прерываем цикл
break
if is_sorted: # Если массив отсортирован => прерываем бесконечный цикл
break
else: # Иначе перемешиваем список заново
shuffle(a)
print(a) # Наконец, выводим получившийся списокЭтот алгоритм работает случайным образом и может выполняться бесконечно долго. Поэтому использовать его в прикладных системах было бы крайне опасно и неэффективно.
Вам нужно вычислить, сколько итераций потребуется алгоритму Bogosort, чтобы в итоге найти решение.
Ввод
Первая строка входных данных содержит одно целое число
n (1 ≤ n ≤ 10).Следующая строка содержит
n целых чисел, разделённых пробелами ( ≤ ≤ ).Вывод
Программа должна вывести количество итераций, необходимых алгоритму Bogosort, чтобы завершить поиск.
Примеры
Входные данные | Выходные данные |
5
5 -1 2 3 9 | 10 |
Объяснение
Число 10 здесь случайно — это могло быть и 2, и 200. При запуске одной и той же программы с одинаковым входом результат может отличаться при каждом запуске.
Другие абсурдные алгоритмы сортировки
Другие визуализированные алгоритмы сортировки можно найти в видео на YouTube, созданном Ardens.
Constraints
Time limit: 60 seconds
Memory limit: 512 MB
Output limit: 1 MB