Алгоритмы сортировки, часть 2

Сортировка вставками — это простой алгоритм сортировки на основе сравнения. Он работает, разделяя входной список на две части: отсортированную часть и несортированную часть.

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

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

Этот процесс повторяется до тех пор, пока весь список не будет отсортирован.

Пошаговое объяснение

  1. Начать с первого элемента: первый элемент в списке считается отсортированным, а остальные элементы считаются несортированными.
  2. Повторить несортированную часть. Повторить каждый элемент несортированной части, начиная со второго элемента (индекс 1).
  3. Выберите элемент из несортированной части. Возьмите текущий элемент из несортированной части и сохраните его в переменной для последующего использования.
  4. Сравнить и сместить. Начиная с крайнего правого элемента, сравните текущий элемент с каждым элементом в отсортированной части. Переместите большие элементы вправо, чтобы освободить место для текущего элемента, который будет помещен на свое место.
  5. Вставить элемент. Поместите текущий элемент на свое место в отсортированном разделе.
  6. Повторить: повторяйте шаги с 3 по 5, пока не будут обработаны все элементы в несортированной части.
  7. Сортированный список. После завершения итерации весь список будет отсортирован.

Сложность времени

Временная сложность в наихудшем случае (список в обратном порядке):

В худшем случае, когда входной список находится в обратном порядке, алгоритм выполняет максимальное количество сравнений и сдвигов для каждого элемента в несортированной части.

Для каждого элемента i в несортированной части его необходимо сравнить и сдвинуть i раз в отсортированной части. Таким образом, общее количество сравнений и сдвигов будет суммой первых n натуральных чисел, что пропорционально n². Следовательно, временная сложность в наихудшем случае составляет O (n²).

Временная сложность наилучшего случая (уже отсортированный список):

В лучшем случае, когда входной список уже отсортирован, алгоритм выполняет только n-1 сравнений и не выполняет никаких сдвигов, так как каждый элемент больше предыдущего в отсортированной части. Таким образом, временная сложность в лучшем случае составляет O (n).

Код

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        # Pick the current element to be inserted in the sorted portion
        current_element = arr[i]
        j = i - 1

        # Compare and shift elements to make space for the current element
        while j >= 0 and arr[j] > current_element:
            arr[j + 1] = arr[j]
            j -= 1

        # Insert the current element at its correct position
        arr[j + 1] = current_element

# Example usage:
input_list = [5, 2, 9, 1, 5, 6]
insertion_sort(input_list)
print(input_list)

Пояснение к примеру

Список: Отсортированная часть [5], Несортированная часть [2, 9, 1, 5, 6].

Итерация 1:

  • Выберите 2 из несортированной части и сравните с 5.
  • Сдвиньте 5 вправо и вставьте 2 в первую позицию.
  • Отсортированная часть: [2, 5] Неотсортированная часть: [9, 1, 5, 6].

Итерация 2:

  • Выберите 9 из несортированной части и сравните его с 5.
  • Начиная с 9 > 5, он уже находится в правильном положении.
  • Отсортированная часть: [2, 5, 9] Неотсортированная часть: [1, 5, 6].

Итерация 3:

  • Выберите 1 из несортированной части и сравните его с 9.
  • Сдвиньте 9 вправо.
  • Сравните 1 с 5.
  • Сдвиньте 5 вправо.
  • Сравните 1 с 2.
  • Сдвиньте 2 вправо и вставьте 1 в первую позицию.
  • Отсортированная часть: [1, 2, 5, 9] Неотсортированная часть: [5, 6].

Итерация 4:

  • Выберите 5 из несортированной части и сравните его с 9.
  • Сдвиньте 9 вправо.
  • Сравните 5 с 5 (самим собой).
  • Элемент уже находится в правильном положении.
  • Отсортированная часть: [1, 2, 5, 9] Неотсортированная часть: [6].

Итерация 5:

  • Выберите 6 из несортированной части и сравните его с 9. ,
  • Сдвиньте 9 вправо.
  • Сравните 6 с 5. Сдвиньте 5 вправо и вставьте 6 в третью позицию.
  • Отсортированная часть: [1, 2, 5, 6, 9] Неотсортированная часть: [].

Алгоритм завершен, и отсортированный список равен [1, 2, 5, 6, 9].