Визуализация
Данные: Случайные
Легенда цветов
Как работает сортировка вставками
Идея алгоритма. Представьте, что вы играете в карты и берете новую карту со стола. Вы смотрите на свои карты (которые уже отсортированы в руке) и вставляете новую карту между нужными. Точно так же работает и этот алгоритм.
Алгоритм действий:
- Считаем, что первый элемент (индекс 0) уже отсортирован.
- Берем следующий неотсортированный элемент. Запоминаем его значение (назовем `key`).
- Сравниваем `key` с отсортированными элементами левее него, двигаясь справа налево.
- Если отсортированный элемент больше `key`, мы сдвигаем этот элемент на одну позицию вправо, чтобы освободить место.
- Как только находим элемент, который меньше или равен `key` (или достигаем начала массива), вставляем `key` в освободившуюся позицию.
- Повторяем шаги 2-5 для всех оставшихся элементов.
- Случайные - в среднем каждый элемент сравнивается и сдвигается на половину отсортированной части. Сложность O(n²).
- В обратном порядке - наихудший случай. Каждый новый элемент оказывается самым маленьким и тянется до самого начала массива. Сдвигов больше всего.
- Отсортированные - наилучший случай. Каждый элемент при первом же сравнении оказывается больше предыдущего, сдвигов нет вообще. Сложность O(n).
- Почти отсортированные - алгоритм работает очень быстро, так как элементы сдвигаются лишь на пару позиций. Из-за этого сортировка вставками часто применяется на практике для небольших или почти отсортированных массивов.
- Одинаковые - сдвигов не происходит, так как алгоритм устойчив и не меняет порядок равных элементов. Работает за O(n).
Сложность алгоритма
Сортировка вставками - это алгоритм с квадратичной сложностью в худшем и среднем случае, но с линейной - в лучшем. Это делает ее адаптивной: чем "ровнее" входной массив, тем быстрее она работает. График сложности можно посмотреть тут.
По времени
| Случай | Время | Комментарий |
|---|---|---|
| Лучший | O(n) | Массив уже отсортирован. По одному сравнению на элемент, 0 сдвигов |
| Средний | O(n²) | В среднем каждый элемент сдвигает половину левой части |
| Худший | O(n²) | Массив отсортирован в обратном порядке. Максимальное число сдвигов |
По памяти
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Дополнительная память | O(1) | Сортировка происходит "на месте" (in-place). Нужна только одна переменная для хранения текущего элемента (key) |
Устойчивость алгоритма
Устойчивой называется сортировка, которая не меняет взаимный порядок равных элементов.
| Характеристика | Оценка | Комментарий |
|---|---|---|
| Устойчивость | Да | Алгоритм сдвигает элементы только если они строго больше `key`. Равные элементы остаются в исходном относительном порядке. |
Примеры реализации сортировки вставками
Код на C
void insertion_sort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
// Сдвигаем элементы, которые больше key, вправо
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
// Вставляем key на правильное место
arr[j + 1] = key;
}
}Код на Python
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
# Сдвигаем элементы, которые больше key, вправо
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
# Вставляем key на правильное место
arr[j + 1] = key
return arrКод на JavaScript
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
let key = arr[i];
let j = i - 1;
// Сдвигаем элементы, которые больше key, вправо
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
// Вставляем key на правильное место
arr[j + 1] = key;
}
return arr;
}Хотите разобрать тему глубже? В нашем бесплатном курсе есть урок про сортировку вставками - с подробной теорией, задачами и проверочными вопросами.