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