Перед выходом в рейд гильдия строится в колонну: слабые впереди, сильные в хвосте — чтобы последний прикрывал отход, а не наоборот.
Отсортируй силы бойцов по неубыванию методом выбора максимума: найди самого сильного среди тех, кто ещё не занял своё место в хвосте, и поменяй его местами с последним «неразобранным» бойцом. Дальше повтори то же самое с оставшейся частью колонны — и так, пока колонна не кончится.
Входные данные
В первой строке — одно натуральное число N, не превосходящее 1000. Во второй строке — N целых чисел, не превосходящих по модулю 1000: силы бойцов.
Выходные данные
Вывести силы бойцов в порядке построения — в одну строку через пробел.
Пример
Входные данные:
5
3 1 4 1 5
Выходные данные:
1 1 3 4 5
Ограничение. Встроенная сортировка запрещена: ни sort(), ни sorted(), ни чужая функция, которая сортирует за тебя. Проверяющий смотрит не на ответ, а на то, как ты его получил — правильный ответ неправильным методом здесь стоит меньше, чем аккуратный алгоритм.
Максимум тоже ищи сам, циклом: max() и index() в этой задаче отложи в сторону, они и есть тот самый шаг, который надо показать.
Как это оценивается — 5 баллов
- Считаны N и все N чисел, программа работает с массивом целиком, а не с отдельными переменными.
- Максимум неразобранной части ищется явным циклом сравнения, и запоминается его индекс, а не только значение.
- Найденный максимум ставится на место обменом двух элементов того же массива — новый список рядом не строится.
- Внешний цикл повторяет шаг, каждый раз укорачивая неразобранную часть на один; в конце массив упорядочен по неубыванию.
- Результат выведен одной строкой через пробел — без скобок, запятых и лишних слов.
Минус. Если всю работу сделает sorted(), сортировка в программе будет, а твоего алгоритма — нет. Ответ верный, метод отсутствует, баллы соответствующие.