Сортировка вставками (Insertion Sort) является простым алгоритмом сортировки, который работает путем постепенного построения отсортированной последовательности. Он начинает с второго элемента массива и вставляет его в правильную позицию в уже отсортированной части массива. Алгоритм продолжает это для каждого элемента, пока не завершит сортировку всего массива. Вот код на Python для сортировки вставками со всеми пояснениями:

python

def insertion_sort(arr):

    # Начинаем со второго элемента (индекс 1), так как первый элемент считается уже отсортированным

    for i in range(1, len(arr)):

        current_element = arr[i]  # Текущий элемент, который нужно вставить в отсортированную часть

        j = i - 1  # Индекс предыдущего элемента

        

        # Сравниваем текущий элемент с предыдущим элементом в отсортированной части

        while j >= 0 and current_element < arr[j]:

            arr[j + 1] = arr[j]  # Перемещаем элемент вправо

            j -= 1

        

        arr[j + 1] = current_element  # Вставляем текущий элемент в правильную позицию

        

    # После завершения цикла весь массив будет отсортирован



# Пример использования

my_list = [64, 34, 25, 12, 22, 11, 90]

insertion_sort(my_list)

print("Отсортированный список:", my_list)

Давайте рассмотрим каждую часть кода: 1. Функция `insertion_sort(arr)` принимает список `arr`, который мы хотим отсортировать в порядке возрастания. 2. Мы начинаем цикл `for` с индекса 1, так как первый элемент уже считается отсортированным. 3. `current_element` - текущий элемент, который мы хотим вставить в отсортированную часть. 4. Мы создаем переменную `j`, чтобы указать на предыдущий элемент списка для сравнения с `current_element`. 5. Запускаем цикл `while`, который продолжает перемещать элементы вправо, пока текущий элемент меньше предыдущего элемента в отсортированной части. 6. После того как мы нашли правильное место для `current_element`, мы вставляем его в массив. 7. После завершения цикла `for`, весь массив будет отсортирован. 8. Мы используем пример с несортированным списком `my_list`, применяем `insertion_sort(my_list)` и выводим отсортированный список с помощью `print`. Этот код демонстрирует работу алгоритма сортировки вставками на Python. После выполнения этой функции `insertion_sort`, список `my_list` будет отсортирован в порядке возрастания.