Начало
Учебные материалы
Методы уменьшения размера задачи
Идея методов уменьшения размера задачи Сортировка вставками Поиск в глубину и поиск в ширину Алгоритмы генерации комбинаторных объектов Бинарный поиск Задача поиска фальшивой монеты Задача выбора Онлайновые алгоритмы
Сортировка вставками
Следуя идее метода, полагаем, что задача меньшего размера, а именно сортировка массива `A[0...n-2]`, уже решена и мы имеем
отсортированный массив размером `n-1`: `A[0] <= A[1] <=...<= A[n-2]`.
Чтобы воспользоваться решением задачи меньшего размера для получения
решения исходной задачи, нужно добавить в это решение элемент `A[n-1]`.
Для этого -- найти нужную позицию среди отсортированных элементов
и вставить туда элемент `A[n-1]`.
--
Есть три подходящих способа сделать это.
1. Мы можем просматривать отсортированный подмассив слева направо, пока не достигнем первого
элемента, большего или равного `A[n-1]`, и после этого осуществить вставку `A[n-1]`
непосредственно перед найденным элементом.
2. Мы можем просматривать подмассив справа налево, пока не найдем первый элемент, меньший или
равный `A[n-1]`, и затем вставить `A[n-1]` непосредственно за ним.
По сути, оба варианта эквивалентны; на практике обычно используется второй способ,
поскольку он лучше работает с отсортированными или почти отсортированными
массивами (почему?).
--
Получившийся в результате алгоритм сортировки
называется сортировкой простыми вставками или сортировкой вставками.
3. Для определения позиции вставки элемента `A[n-1]` в отсортированную часть
массива мы используем бинарный поиск.
Получающийся при этом алгоритм носит название сортировки бинарными вставками.
--
Более эффективной будет нерекурсивная реализация этого алгоритма, т.е. снизу вверх.
Элемент `A[i]` (начиная с элемента `A[1]` и заканчивая `A[n-1]`) вставляется в
соответствующее место среди первых `i` элементов массива (которые к этому моменту
уже отсортированы).
`ubrace(A_0 <= ... <= A_j)_("элементы"<=A_i) overset(darr A_i)(<) ubrace(A_{j+1} <= ... <= A_{i-1})_("элементы">A_i) \ | \ A_i, ..., A_{n-1}`
--
Алгоритм InsertionSort (`A`)
// Входные данные: Массив `A[0...n-1]` из `n` элементов
// Выходные данные: Массив `A[0...n-1]`, отсортированный
// в неубывающем порядке
**for** `i in [1...n-1]` **do**
`quad v larr A[i]`
`quad j larr i-1`
`quad` **while** `j>=0` **and** `A[j] > v` **do**
`quad quad quad A[j + 1] larr A[j]`
`quad quad quad j larr j-1`
`quad A[j+1] larr v`
--
Базовой операцией алгоритма является сравнение `A[j] > v`.
Количество сравнений в этом алгоритме зависит от
природы входных данных. В худшем случае сравнение `A[j] > v` выполняется
наибольшее количество раз, т.е. для всех `j = i -1,..., 0`.
Поскольку `v = A[i]`, это означает, что `A[j] > A[i]` для `j = i -1,..., 0`.
Таким образом, для наихудшего случая мы получаем `A[0] > A[1], A[1] > A[2], ..., A[n-2] > А [n-1]`, т.е.
в наихудшем случае входные
данные представляют собой массив строго уменьшающихся значений.
Количество сравнений ключей для таких входных данных равно
`C_{"worst"}(n)=sum_{i=1}^{n-1} sum_{j=0}^{i-1} 1 = (n(n-1))/2 in Theta(n^2)`
--
В лучшем случае сравнение `A[j] > v` выполняется только один раз на каждой
итерации внешнего цикла. Это происходит тогда и только тогда, когда `A[i-1] <= A[i]`
для всех `i in 1,...,n-1`, т.е. если входной массив уже отсортирован
в возрастающем порядке.
Для отсортированного входного
массива количество сравнений ключей равно
`C_{"best"}(n)=sum_{i=1}^{n-1} 1 = n-1 in Theta(n)`
--
Сортировка вставками имеет аналогичную эффективность и для почти
отсортированных массивов, в отличие от рассмотренных ранее сортировок, что можно использовать
для улучшения быстрой сортировки, прекращая рекурсию, когда
подмассивы будут содержать меньше 10 элементов. По окончании такого процесса
весь исходный массив почти отсортирован, и мы можем завершить нашу
работу, применив сортировку вставками. Такое видоизменение алгоритма
позволяет уменьшить общее время сортировки примерно на 10%.
Строгий анализ эффективности алгоритма в среднем случае дает
`C_{"avg"}(n)~~n^2/4 in Theta(n^2)`
