zhenskayaterritoriya.ru
Алгоритм сортировки вставками - один из простых методов сортировки элементов в массиве. Он относится к классу алгоритмов сортировки «на месте», т.е. сравнивает и переставляет значения элементов только внутри исходного массива, без использования дополнительной памяти.
Принцип работы алгоритма сортировки вставками основан на разделении массива на две части: упорядоченную и неупорядоченную. Вначале упорядоченная часть состоит только из одного первого элемента, а неупорядоченная часть содержит все остальные элементы. На каждом шаге берется первый элемент неупорядоченной части и вставляется в правильное место в упорядоченной части. Затем граница между упорядоченной и неупорядоченной частью сдвигается на одну позицию вправо, и процесс повторяется, пока неупорядоченная часть не будет пустой.
Пример работы алгоритма сортировки вставками можно проиллюстрировать на примере сортировки списка чисел: [4, 2, 1, 3, 5]. В начале упорядоченная часть содержит только первый элемент [4], а неупорядоченная - все остальные элементы [2, 1, 3, 5].
На первом шаге берется первый элемент неупорядоченной части (2) и вставляется в упорядоченную часть перед элементом 4, таким образом упорядоченная часть становится равной [2, 4], а неупорядоченная - [1, 3, 5].
Принцип работы алгоритма сортировки вставками
- Берется элемент из неотсортированной части массива и помещается на свое место в отсортированной части массива.
- Отсортированная часть массива увеличивается на один элемент, а неотсортированная часть уменьшается на один элемент.
- Этот процесс повторяется, пока неотсортированная часть массива не станет пустой.
На каждом шаге внутренний цикл сравнивает текущий элемент со всеми предыдущими элементами в отсортированной части массива и вставляет его в правильную позицию. Таким образом, на каждом шаге отсортированная часть массива увеличивается, а неотсортированная часть уменьшается.
Алгоритм сортировки вставками обладает следующими особенностями:
- Стабильность: порядок элементов с одинаковыми значениями сохраняется.
- Эффективность для небольших и почти упорядоченных массивов.
- Временная сложность O(n^2) в худшем и среднем случае, O(n) в лучшем случае, где n - количество элементов в массиве.
- Ин-плейс сортировка: требуется всего один дополнительный элемент для временного хранения значения при сравнении и вставке.
Примеры использования алгоритма сортировки вставками в Python
Пример 1:
Дан массив чисел [9, 3, 12, 5, 1]. Используя алгоритм сортировки вставками, мы можем отсортировать его следующим образом:
Шаг 1: [9, 3, 12, 5, 1] - исходный массив
Шаг 2: [3, 9, 12, 5, 1] - вставляем 3 перед 9
Шаг 3: [3, 9, 12, 5, 1] - 12 уже находится на своем месте
Шаг 4: [3, 5, 9, 12, 1] - вставляем 5 перед 9
Шаг 5: [1, 3, 5, 9, 12] - вставляем 1 перед 3
Таким образом, отсортированный массив будет равен [1, 3, 5, 9, 12].
Пример 2:
Дан массив строк ['cat', 'dog', 'apple', 'banana']. Используя алгоритм сортировки вставками с учетом лексикографического порядка, мы можем отсортировать его следующим образом:
Шаг 1: ['cat', 'dog', 'apple', 'banana'] - исходный массив
Шаг 2: ['cat', 'dog', 'apple', 'banana'] - 'dog' уже находится на своем месте
Шаг 3: ['apple', 'cat', 'dog', 'banana'] - вставляем 'apple' перед 'cat'
Шаг 4: ['apple', 'banana', 'cat', 'dog'] - вставляем 'banana' перед 'cat'
Таким образом, отсортированный массив будет равен ['apple', 'banana', 'cat', 'dog'].
Алгоритм сортировки вставками широко используется в программировании для сортировки массивов. Он эффективен для небольших массивов и массивов, которые уже почти отсортированы.