#231

Вставка числа

Темы: [Сортировка вставками]

Требуется вставить в данный массив на данное место данный элемент, сдвинув остальные элементы вправо.

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

В первой строке вводится одно натуральное число, не превосходящее 1000 – размер массива. Во второй строке задаются N чисел – элементы массива (целые числа, не превосходящие по модулю 1000). В третьей строке вводится число, которое необходимо вставить, и номер места, на которое его нужно вставить.

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

Вывести получившийся массив.

Примеры

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

5
1 2 3 4 5
2 3

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

1 2 2 3 4 5

#232

Сортировка вставками

Темы: [Сортировка вставками]

Требуется отсортировать массив по неубыванию методом "вставок".

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

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

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

Вывести получившийся массив.

Примеры

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

5
5 4 3 2 1

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

1 2 3 4 5

#1436

Библиотечный метод

Темы: [Сортировка вставками]

Продемонстрируйте работу метода сортировки вставками по возрастанию. Для этого выведите состояние данного массива после каждой вставки на отдельных строках. Если массив упорядочен изначально, то следует не выводить ничего.

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

На первой строке дано число (1 ≤ N ≤ 100) – количество элементов в массиве. На второй строке задан сам массив: последовательность натуральных чисел, не превышающих 10⁹.

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

В выходной файл выведите строки (по количеству вставок) по N чисел каждая.

Примеры

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

2
2 1

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

1 2

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

4
2 1 5 3

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

1 2 5 3 
1 2 3 5

#111157

Сортировка вставкой

Темы: [Сортировка вставками]

Дан список целых чисел. Отсортируйте его в порядке неубывания значений. Выведите полученный список на экран.

Решите эту задачу при помощи алгоритма сортировки вставкой.Решение оформите в виде функции InsertionSort(A).

В этой задаче нельзя пользоваться дополнительным списком операциями удаления и вставки элементов.

В алгоритме сортировки вставкой в каждый произвольный момент начальная часть массива уже отсортирована. В решении имеется цикл for i in range(1, len(A)), внутри которого предположении, что элементы списка A[0],A[1], ..., A[i-1]уже отсортированы, элемент A[i]добавляется в отсортированную часть списка.Для этого находится позиция, в которую необходимо вставить элемент A[i], затем осуществляется циклический сдвиг фрагмента уже отсортированной части.

Примеры

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

1 4 2 3 4

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

1 2 3 4 4