Алгоритмы сортировки, часть 2
Сортировка вставками — это простой алгоритм сортировки на основе сравнения. Он работает, разделяя входной список на две части: отсортированную часть и несортированную часть.
Первоначально отсортированная часть содержит только первый элемент входного списка, а несортированная часть содержит остальные.
Затем алгоритм перебирает несортированную часть, содержащую все остальное. Затем алгоритм перебирает несортированную часть по одному элементу за раз и вставляет каждый элемент в правильное положение в отсортированной части.
Этот процесс повторяется до тех пор, пока весь список не будет отсортирован.
Пошаговое объяснение
- Начать с первого элемента: первый элемент в списке считается отсортированным, а остальные элементы считаются несортированными.
- Повторить несортированную часть. Повторить каждый элемент несортированной части, начиная со второго элемента (индекс 1).
- Выберите элемент из несортированной части. Возьмите текущий элемент из несортированной части и сохраните его в переменной для последующего использования.
- Сравнить и сместить. Начиная с крайнего правого элемента, сравните текущий элемент с каждым элементом в отсортированной части. Переместите большие элементы вправо, чтобы освободить место для текущего элемента, который будет помещен на свое место.
- Вставить элемент. Поместите текущий элемент на свое место в отсортированном разделе.
- Повторить: повторяйте шаги с 3 по 5, пока не будут обработаны все элементы в несортированной части.
- Сортированный список. После завершения итерации весь список будет отсортирован.
Сложность времени
Временная сложность в наихудшем случае (список в обратном порядке):
В худшем случае, когда входной список находится в обратном порядке, алгоритм выполняет максимальное количество сравнений и сдвигов для каждого элемента в несортированной части.
Для каждого элемента 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]
.