Задача 80: Сортировка вставками

Условие задачи:

Реализуйте алгоритм сортировки вставками, который заключается в том, что мы просматриваем последовательно \(a_2,a_3,a_4, \ldots ,a_n\) и каждый новый элемент \(a_i\) вставляем на подходящее место в уже упорядоченную совокупность \(a_1,a_2,\ldots,a_{i−1}\). Это место определяется последовательным сравнением \(a_i\) с упорядоченными элементами \(a_{i−1},\ldots,a_1\)
и обменом с теми элементами, которые больше, чем \(a_i\).Такой алгоритм называется сортировкой вставками. Именно его обычно использует человек в быту при упорядочении предметов, например библиографических карточек в каталоге библиотеки.

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

На вход программе сначала подается значение \(n <= 100000\) – количество элементов в массиве. В следующей строке входных данных расположены сами элементы массива – целые числа, по модулю не превосходящие \(10000\).

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

Распечатайте отсортированный по неубыванию массив.

Решение:

def insertion_sort(nums):  
    for i in range(1, len(nums)):
        item_to_insert = nums[i]
        j = i - 1
        while j >= 0 and nums[j] > item_to_insert:
            nums[j + 1] = nums[j]
            j -= 1
        nums[j + 1] = item_to_insert


n = input()
numss = list(map(int, input().split())) 
insertion_sort(numss)  

print(*numss)

У вас включен блокировщик рекламы. Пожалуйста, выключите его чтобы увидеть решения. На этом сайте не так много рекламы, а кушать что-то надо. Вот котик