Сортировка вставками, также известная как "сортировка прямыми вставками", является одним из простых алгоритмов сортировки. Он основан на том, что элементы в список вставляются в уже отсортированную часть списка на свое место.
Алгоритм сортировки вставками просто проходит по списку элементов и для каждого элемента находит его положение в отсортированной части списка и вставляет его туда. Это продолжается до тех пор, пока все элементы не будут отсортированы.
Вот как выглядит алгоритм сортировки вставками в Python:
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key
# Пример использования
arr = [5, 2, 9, 1, 3]
insertion_sort(arr)
print(arr)
В этом примере мы создаем функцию insertion_sort, которая принимает список arr в качестве аргумента. С помощью цикла for проходим по всем элементам списка, начиная со второго элемента (индекс 1), поскольку первый элемент можно считать уже отсортированным.
Внутри цикла нашего алгоритма мы сохраняем текущий элемент в переменной key. Затем мы находим его правильное положение в уже отсортированной части списка, двигаясь в обратном направлении с помощью вложенного цикла while. Если элемент больше key, мы сдвигаем его на одну позицию вправо. После нахождения правильного места мы вставляем key на это место.
После завершения работы алгоритма список будет отсортирован в порядке возрастания: [1, 2, 3, 5, 9].
Сортировка вставками имеет время выполнения O(n^2), что означает, что время выполнения алгоритма увеличивается квадратично по мере увеличения размера списка. Однако, в отличие от других алгоритмов сортировки с квадратичной сложностью, таких как сортировка пузырьком или сортировка выбором, сортировка вставками имеет лучшую производительность для почти отсортированных списков или для списков с небольшим количеством элементов.
Таким образом, сортировка вставками - это простой и эффективный алгоритм сортировки, особенно для маленьких списков или частично отсортированных списков.