TUZ_5-05 Подсчет количества раундов обработки чисел в порядке возрастания
5.5. Подсчет количества раундов обработки чисел в порядке возрастания
В этом задании дается массив чисел, возможно несортированный. Массив заполнен числами от 0 до n – 1.
Цель этого задания – подсчитать количество раундов перестановки чисел, необходимых для упорядочения их в порядке возрастания.
В первом раунде обрабатываются числа в порядке возрастания.
В последующих раундах обрабатываются числа, которые не были обработаны в предыдущих раундах,
и снова в порядке возрастания.
Этот процесс повторяется до тех пор, пока не будут обработаны все числа в порядке возрастания.
Для примера рассмотрим список L = [0, 4, 3, 5, 2, 1].
В первом раунде обрабатываются числа 3, 2 и 1 в порядке возрастания,
[0, 4, 3, 5, 2, 1] -> [0, 3, 4, 5, 2, 1] -> [0, 3, 4, 2, 5, 1]-> [0, 3, 4, 2, 1, 5]
во втором раунде – только 2 и 1 ,
[0, 3, 4, 2, 1, 5] -> [0, 3, 2, 4, 1, 5] -> [0, 3, 2, 1, 4, 5]
в третьем раунде – тоже 2 и 1,
[0, 3, 2, 1, 4, 5] -> [0, 2, 3, 1, 4, 5] -> [0, 2, 1, 3, 4, 5]
и в четвертом раунде – 1: [0, 1, 2, 3, 4, 5]
Следовательно, для обработки данного списка L в порядке возрастания требуется четыре раунда.
Ваша задача: написать функцию, которая принимает перестановку чисел от 0 до n – 1 и возвращает количество раундов.
В табл. 5.5 показаны ожидаемые результаты для некоторых входных данных.
| Таблица 5.5. Некоторые ожидаемые результаты для задачи подсчета раундов обработки чисел в порядке возрастания |
| Perm |
Ожидаемый результат |
| 0, 1, 5, 4, 2, 3 |
3 |
| 0, 1, 2, 4, 3, 5 |
2 |
| 4, 11, 2, 8, 6, 9, 5, 3, 0, 10, 1, 12, 7 |
6 |
| 0, 1, 4, 3, 2 |
3 |