1.1 Сортировки — Рука картёжника: сортировка вставками

Задача 98541
Условие задачи

В таверне «Астролита» между рейдами играют в карты. Опытный игрок разбирает руку так: берёт карты по одной слева направо и каждую новую вставляет на своё место среди тех, что уже разобраны, — сдвигая соседей вправо, пока не найдётся щель.

Отсортируй массив по неубыванию методом вставок — ровно так, как разбирают руку.

Входные данные

В первой строке — одно натуральное число N, не превосходящее 1000. Во второй строке — N целых чисел, не превосходящих по модулю 1000: достоинства карт.

Выходные данные

Вывести разобранную руку — в одну строку через пробел.

Пример

Входные данные:
5
5 4 3 2 1

Выходные данные:
1 2 3 4 5

Ограничение. Встроенная сортировка запрещена: ни sort(), ни sorted(), ни чужая функция, которая сортирует за тебя. Проверяющий смотрит не на ответ, а на то, как ты его получил — правильный ответ неправильным методом здесь стоит меньше, чем аккуратный алгоритм.

Метод insert() здесь тоже нельзя: он делает сдвиг за тебя, а сдвиг — это и есть та часть, ради которой задача написана.

Как это оценивается — 5 баллов

  • Считаны N и все N чисел, дальше программа работает с массивом.
  • Внешний цикл идёт со второго элемента: первая карта уже считается разобранной. Текущий элемент сохранён в переменную, иначе его затрёт первый же сдвиг.
  • Внутренний цикл двигает вправо элементы разобранной части, которые больше текущего (или меняет текущий с соседом местами), — и останавливается на первом, который не больше.
  • Текущий элемент опускается в освободившееся место; цикл не выходит за левый край массива.
  • Результат выведен одной строкой через пробел.

Минус. a.insert(...) и sorted() — это чужая работа. За чужую работу баллы получает тот, кто её сделал, а он в ведомости не значится.

0 / 5 баллов
Тренировка — проверяйте части и берите подсказки по ходу.
Для проверки решения задачи необходимо зарегистрироваться или авторизоваться!
Ваше решение