Сортировка вставками (Insertion sort)
Сортировка вставками очень похожа на алгоритм сортировки выбором (selection sort). Она интуитивно понятна и также поддерживает отсортированную левую часть массива, постепенно продвигаясь к концу массива.
Если говорить подробнее, в алгоритме сортировки вставками мы начинаем с самого левого элемента и двигаемся дальше направо. Как только встречаем элемент, который меньше тех, что находятся слева от него, мы сдвигаем все элементы по одному вправо, чтобы освободить место и поставить это значение на корректную позицию. Например, если у нас есть массив
[0, 2, 4, 1, 10, 8] и мы сейчас рассматриваем элемент 1, то сначала сдвигаем вправо 4, затем 2, а затем вставляем 1 между 0 и 2, получая [0, 1, 2, 4, 10, 8]. После этого переходим к следующему элементу 10. Ничего не делаем, так как он больше всех элементов слева. Затем берем 8 и сдвигаем 10 вправо, чтобы поставить 8 между 4 и 10.a = [...]
for i in range(1, len(a)): # начинаем со второго элемента
while i > 0 and a[i] < a[i - 1]: # пока текущий элемент меньше предыдущего
a[i - 1], a[i] = a[i], a[i - 1] # меняем местами текущий элемент с предыдущим
i -= 1 # следим за индексом текущего элемента
print(a)Алгоритм сортировки вставками вставляет текущий элемент на правильное место в уже обработанной части массива. В худшем случае, если элементы массива упорядочены по убыванию, для каждого
i придется сдвигать все предыдущие элементы, чтобы расположить текущий элемент на нужную позицию. Это приведет к суммарным операциям.Давайте пошагово разберем, как работает этот алгоритм на нескольких примерах:
[4, 1, -1, 0, 2, 8]
i = 1⇒ перестановка ⇒[1, 4, -1, 0, 2, 8]
i = 2⇒ перестановка ⇒[1, -1, 4, 0, 2, 8]⇒ перестановка ⇒[-1, 1, 4, 0, 2, 8]
i = 3⇒ ничего не делаем
i = 4⇒ перестановка ⇒[-1, 1, 0, 4, 2, 8]⇒ перестановка ⇒[-1, 0, 1, 2, 4, 8]
i = 5⇒ ничего не делаем
- выводим
[-1, 0, 1, 2, 4, 8]
[10, 5, 1, -7]
i = 1⇒ перестановка ⇒[5, 10, 1, -7]
i = 2⇒ перестановка ⇒[5, 1, 10, -7]⇒ перестановка ⇒[1, 5, 10, -7]
i = 3⇒ перестановка ⇒[1, 5, -7, 10]⇒ перестановка ⇒[1, -7, 5, 10]⇒ перестановка ⇒[-7, 1, 5, 10]
[1, 2, 3, 4, 5]
i = 1⇒ ничего не делаем
i = 2⇒ ничего не делаем
i = 3⇒ ничего не делаем
i = 4⇒ ничего не делаем
Задание
Дано n целых чисел. Отсортируйте их по возрастанию, используя сортировку вставками.
Ввод
В первой строке задается одно целое число
n (1 ≤ n ≤ 1000) — количество элементов в массиве.Во второй строке содержится
n целых чисел (от до ).Вывод
Программа должна вывести массив из входных данных, отсортированный по возрастанию.
Примеры
Ввод | Вывод |
5
5 5 3 2 3 | 2 3 3 5 5 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB