Задача 367: сортировка Бозо
Сортировка Bozo, чтобы не путать с немного менее эффективной сортировкой bogo, состоит в проверке, сортируется ли входная последовательность и если не произвольно меняет два элемента. Это повторяется до тех пор, пока в итоге последовательность не будет отсортирована.
Если мы рассмотрим все перестановки первых 4 натуральных чисел в качестве входных значений математического ожидания числа свопов, усредненных по всем 4! входные последовательности - 24,75. Уже отсортированная последовательность занимает 0 шагов.
В этой задаче рассмотрим следующий вариант на сортировке bozo. Если последовательность не в порядке, мы произвольно выбираем три элемента и произвольно перемешиваем эти три элемента. Все 3! = 6 перестановок этих трех элементов одинаково вероятны. Уже отсортированная последовательность займет 0 шагов. Если мы рассмотрим все перестановки первых 4 натуральных чисел в качестве входных значений математического ожидания количества перетасов, усредненных по всем 4! входные последовательности - 27,5. Рассмотрим в качестве входных последовательностей перестановки первых 11 натуральных чисел. Осредненный по всем 11! входные последовательности, каково ожидаемое количество тасований, которое будет выполнять этот алгоритм сортировки?
Дайте ваш ответ округленным до ближайшего целого.