Дано число
N (
\(1<=N<=1000\)), а затем
N натуральных чисел из диапазона от
1 до
100.
Вывести перестановку элементов массива, на которой быстрая сортировка выполнит максимальное число сравнений, при условии, что
"опорным" будет элемент посередине.
Входные данные
В первой строке задаётся число
N.
Выходные данные
Выведите требуемую перестановку чисел от
1 до
N, на которой быстрая сортировка выполнит максимальное число сравнений.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
5 |
1 4 5 3 2 |
Пояснение
Худшее время работы достигается когда массив разбивается так, что одна часть содержит n−1 элементов, а вторая — 1. Этого можно добиться если на каждом этапе разбиения в середине будет максимальный элемент.
1)
1 4 5 3 2
2)
1 4 2 3 5
3)
1 3 2 4 5
4)
1 2 3 4 5
5)
1 2 3 4 5