Я только начал изучать Python. Уже очень долго никак не могу решить одну задачу:
Условие:
Продемонстрируйте работу метода сортировки вставками по возрастанию. Для этого выведите состояние данного массива после каждой вставки на отдельных строках. Если после рассмотрения очередного элемента массив не изменился, то его выводить не нужно. Если массив упорядочен изначально, то следует не выводить ничего.
Входные данные:
На первой строке дано число 𝑁 (1≤𝑁≤100) — количество элементов в массиве. На второй строке задан сам массив: последовательность натуральных чисел, не превышающих 109.
Выходные данные:
В выходной файл выведите строки (по количеству вставок) по 𝑁 чисел каждая.
Примеры:
Ввод №1:
2
2 1
Вывод №1:
1 2
Ввод №2:
4
2 1 5 3
Вывод №2:
1 2 5 3
1 2 3 5
Мой код:
n = int(input())
a = list(map(int, input().split()))
def insertion_sort(a):
for i in range(1, len(a)):
tmp = a[i]
j = i - 1
while j >= 0 and a[j]>tmp:
a[j + 1] = a[j]
j -= 1
a[j + 1] = tmp
print(' '.join(map(str, a)))
insertion_sort(a)
Я пытался решить эту задачу многократно, но постоянно утыкался в одни и те же проблемы:
1) Когда вводится уже отсортированный список, программа трижды/четырежды раз подряд выводит тот же введённый отсортированный список (хотя по условию, в таком случае она должна ничего не делать);
2) Когда вводится пример №1 (2, 2 1
), то программа ничего не выводит (хотя по условию, в таком случае должна вывести 1 2
).
Мне кажется, тут нужно использовать if…
, но я просто не представляю, какое условие поставить, при котором будет печататься промежуточный неотсортированный список (и при каком не будет печататься ничего). Пожалуйста, помогите! Я уже совсем сбился с толку…