0

Я только начал изучать 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…, но я просто не представляю, какое условие поставить, при котором будет печататься промежуточный неотсортированный список (и при каком не будет печататься ничего). Пожалуйста, помогите! Я уже совсем сбился с толку…

1 ответ 1

1

Традиционный подход, который применяется при указанных вами условиях - введение специального флажка. Например вот так:

def insertion_sort(a):
    for i in range(1, len(a)):
        tmp = a[i]
        j = i - 1
        flag=0
        while j >= 0 and a[j]>tmp:
            a[j + 1] = a[j]
            j -= 1
            flag=flag+1
        a[j + 1] = tmp
        if flag!=0:
            print(' '.join(map(str, a)))

Вызов:

lt=[3,1,8,12,4,9,2,7,5,6]
insertion_sort(lt)

Результат работы:

1 3 8 12 4 9 2 7 5 6
1 3 4 8 12 9 2 7 5 6
1 3 4 8 9 12 2 7 5 6
1 2 3 4 8 9 12 7 5 6
1 2 3 4 7 8 9 12 5 6
1 2 3 4 5 7 8 9 12 6
1 2 3 4 5 6 7 8 9 12

Такой прием следует взять на вооружение.

1
  • Спасибо Вам большое! Вы мне очень помогли! 25 мая 2020 в 21:56

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.