Подразделы

Другие разделы

Дата и время

04/04/2025 13:02:32

Авторизация

Методы уменьшения размера задачи

Идея методов уменьшения размера задачи Сортировка вставками Поиск в глубину и поиск в ширину Алгоритмы генерации комбинаторных объектов Бинарный поиск Задача поиска фальшивой монеты Задача выбора Онлайновые алгоритмы

Сортировка вставками

Рассмотрим применение метода уменьшения на единицу к сортировке массива $A[0...n-1]$ . Следуя идее метода, полагаем, что задача меньшего размера, а именно сортировка массива $A[0...n-2]$ , уже решена и мы имеем отсортированный массив размером $n-1$ : $A[0] <= A[1] <=...<= A[n-2]$ .

Чтобы воспользоваться решением задачи меньшего размера для получения решения исходной задачи, нужно добавить в это решение элемент $A[n-1]$ . Для этого – найти нужную позицию среди отсортированных элементов и вставить туда элемент $A[n-1]$ .

Есть три подходящих способа сделать это.

Мы можем просматривать отсортированный подмассив слева направо, пока не достигнем первого элемента, большего или равного $A[n-1]$ , и после этого осуществить вставку $A[n-1]$ непосредственно перед найденным элементом.
Мы можем просматривать подмассив справа налево, пока не найдем первый элемент, меньший или равный $A[n-1]$ , и затем вставить $A[n-1]$ непосредственно за ним.

По сути, оба варианта эквивалентны; на практике обычно используется второй способ, поскольку он лучше работает с отсортированными или почти отсортированными массивами (почему?).

Получившийся в результате алгоритм сортировки называется сортировкой простыми вставками или сортировкой вставками.

Для определения позиции вставки элемента $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%.