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

Сортировка вставками
Сортировка вставками
Предназначение	Алгоритм сортировки
Структура данных	Массив
Худшее время	О(n2) сравнений, обменов
Лучшее время	O(n) сравнений, 0 обменов
Среднее время	О(n2) сравнений, обменов
Затраты памяти	О(n) всего, O(1) вспомогательный

Сортировка вставками
Сортировка вставками
Предназначение	Алгоритм сортировки
Структура данных	Массив
Худшее время	О(n2) сравнений, обменов
Лучшее время	O(n) сравнений, 0 обменов
Среднее время	О(n2) сравнений, обменов
Затраты памяти	О(n) всего, O(1) вспомогательный

Сортировка вставками (англ. Insertion sort) — алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый элемент размещается в подходящее место среди ранее упорядоченных.

На вход подаётся последовательность из n чисел (ключей), обычно в виде массива; на выходе требуется перестановка исходных элементов, упорядоченная по неубыванию.

Применение бинарного поиска для определения позиции текущего элемента в отсортированной части ускоряет алгоритм; сдвиг массива вправо решается сменой указателей.

Алгоритм обходится без дополнительной памяти, кроме переменной для текущего элемента. В псевдокоде представлены три варианта: со сдвигом через key, через x и с барьерным элементом A[0] = −∞; последний использует swap и работает медленнее.

Время выполнения сортировки вставками растёт с увеличением размера входных данных и зависит от их исходной упорядоченности. В лучшем случае, когда массив уже отсортирован, каждый внутренний цикл выполняется только один раз, поэтому время работы линейно.

Если массив отсортирован в обратном порядке, каждый новый элемент сравнивается со всеми ранее упорядоченными. Суммарное число операций описывается квадратичной функцией от размера входных данных.

Среднее число сравнений для вставки i-го элемента вычисляется при равновероятном попадании в любую из i позиций, при этом даже правильная позиция требует как минимум одного сравнения. Суммирование этих оценок по всем элементам даёт итоговую сложность O(n^2).

Сортировка вставками (англ. Insertion sort) — алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов^[1]. Вычислительная сложность — $O(n^{2})$ .

На вход алгоритма подаётся последовательность $n$ чисел: $a_{1},a_{2},...,a_{n}$ . Сортируемые числа также называют ключами. Входная последовательность на практике представляется в виде массива с $n$ элементами. На выходе алгоритм должен вернуть перестановку исходной последовательности $a_{1}^{'},a_{2}^{'},...,a_{n}^{'}$ , чтобы выполнялось следующее соотношение $a_{1}^{'}\leqslant a_{2}^{'}\leqslant ...\leqslant a_{n}^{'}$ ^[2].

В начальный момент отсортированная последовательность пуста. На каждом шаге алгоритма выбирается один из элементов входных данных и помещается на нужную позицию в уже отсортированной последовательности до тех пор, пока набор входных данных не будет исчерпан. В любой момент времени в отсортированной последовательности элементы удовлетворяют требованиям к выходным данным алгоритма^[3].

Данный алгоритм можно ускорить при помощи использования бинарного поиска для нахождения места текущему элементу в отсортированной части. Проблема с долгим сдвигом массива вправо решается при помощи смены указателей^[1].

На вход процедуре сортировки подаётся массив $A[1..n]$ , состоящий из элементов последовательности $A[1],A[2],...,A[n]$ , которые требуется отсортировать. $n$ соответствует $A.\mathrm {length}$ — размеру исходного массива. Для сортировки не требуется привлечения дополнительной памяти, кроме постоянной величины для одного элемента, так как выполняется перестановка в пределах массива. В результате работы процедуры во входном массиве оказывается требуемая выходная последовательность элементов^[4].

Псевдокод алгоритма:

for j = 2 to A.length do 
    key = A[j]
    i = j-1
    while (int i >= 0 and A[i] > key) do 
        A[i + 1] = A[i]
        i = i - 1
    end while
    A[i+1] = key
end ^[4]

for i = 2 to n do 
    x = A[i]
    j = i
    while (int j > 1 and A[j-1] > x) do 
        A[j] = A[j-1]
        j = j - 1
    end while
    A[j] = x
end for^[5]

A[0] = - $\infty$ 
for i = 2 to n do  
    j = i
    while (j > 0 and A[j] < A[j - 1]) do
        swap (A[j], A[j - 1])
        j = j - 1
    end while
end for^[6]^[7]

В последнем варианте обмен x = A[j]; A[j] = A[j-1]; A[j-1] = x представлен операцией swap из-за чего он немного медленнее. Значение введённого А[0] меньше любого значения остальных элементов^[7].

Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время потребуется для выполнения сортировки. Также на время выполнения влияет исходная упорядоченность массива. Время работы алгоритма для различных входных данных одинакового размера зависит от элементарных операций, или шагов, которые потребуется выполнить^[8].

Для каждой инструкции алгоритма введём временную стоимость и количество повторений, где $t_{j}$ — количество проверок условия во внутреннем цикле while^[9]:

Код	Стоимость	Повторы
for j = 2 to A.length	$c_{1}$	$n$
key = A[j]	$c_{2}$	$n-1$
i = j — 1	$c_{3}$	$n-1$
while i > 0 and A[i] > key	$c_{4}$	$\sum _{j=2}^{n}t_{j}$
A[i+1] = A[i]	$c_{5}$	$\sum _{j=2}^{n}(t_{j}-1)$
i = i — 1	$c_{6}$	$\sum _{j=2}^{n}(t_{j}-1)$
A[i+1] = key	$c_{7}$	$n-1$

Время работы алгоритма сортировки вставками — это сумма времён работы каждого шага^[10]: $T(n)=c_{1}n+c_{2}(n-1)+c_{3}(n-1)+c_{4}\sum _{j=2}^{n}t_{j}+c_{5}\sum _{j=2}^{n}(t_{j}-1)+c_{6}\sum _{j=2}^{n}(t_{j}-1)+c_{7}(n-1)$ .

Самым благоприятным случаем является отсортированный массив. При этом все внутренние циклы состоят всего из одной итерации, то есть $t_{j}=1$ для всех $j$ . Тогда время работы алгоритма составит $T(n)=(c_{1}+c_{2}+c_{3}+c_{4}+c_{7})n-(c_{2}+c_{3}+c_{4}+c_{7})=O(n)$ . Время работы линейно зависит от размера входных данных^[11].

Анализ наихудшего случая

Наихудшим случаем является массив, отсортированный в порядке, обратном нужному. При этом каждый новый элемент сравнивается со всеми в отсортированной последовательности. Это означает, что все внутренние циклы состоят из j итераций, то есть $t_{j}=j$ для всех $j$ . Тогда время работы алгоритма составит:

$T(n)=c_{1}n+c_{2}(n-1)+c_{3}(n-1)+c_{4}\sum _{j=2}^{n}j+c_{5}\sum _{j=2}^{n}(j-1)+c_{6}\sum _{j=2}^{n}(j-1)+c_{7}(n-1)$

$T(n)=c_{1}n+c_{2}(n-1)+c_{3}(n-1)+c_{4}\left({\frac {n(n+1)}{2}}-1\right)+c_{5}{\frac {n(n-1)}{2}}+c_{6}{\frac {n(n-1)}{2}}+c_{7}(n-1)=O(n^{2})$ .

Время работы является квадратичной функцией от размера входных данных^[12].

Анализ среднего случая

Для анализа среднего случая нужно посчитать среднее число сравнений, необходимых для определения положения очередного элемента. При добавлении нового элемента потребуется, как минимум, одно сравнение, даже если этот элемент оказался в правильной позиции. $i$ -й добавляемый элемент может занимать одно из $i+1$ положений. Предполагая случайные входные данные, новый элемент равновероятно может оказаться в любой позиции^[13]. Среднее число сравнений для вставки $i$ -го элемента^[14]:

$T_{i}={\frac {1}{i+1}}\left(\sum _{p=1}^{i}p+i\right)={\frac {1}{i+1}}\left({\frac {i(i+1)}{2}}+i\right)={\frac {i}{2}}+1-{\frac {1}{i+1}}$

Для оценки среднего времени работы для $n$ элементов нужно просуммировать^[15]:

$T(n)=\sum _{i=1}^{n-1}T_{i}=\sum _{i=1}^{n-1}\left({\frac {i}{2}}+1-{\frac {1}{i+1}}\right)=\sum _{i=1}^{n-1}{\frac {i}{2}}+\sum _{i=1}^{n-1}1-\sum _{i=1}^{n-1}\left({\frac {1}{i+1}}\right)$

$T(n)\approx {\frac {n^{2}-n}{4}}+(n-1)-(\ln(n)-1)=O(n^{2})$

Временная сложность алгоритма — $O(n^{2})$ . Однако, из-за константных множителей и членов более низкого порядка алгоритм с более высоким порядком роста может выполняться для небольших входных данных быстрее, чем алгоритм с более низким порядком роста^[16].

↑ ¹ ² Кнут Д. Э. 5.2 Внутренняя сортировка // Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с. — ISBN 5-8459-0082-1.
↑ Кормен, 2013, p. 38.
↑ Кормен, 2013, p. 39.
↑ ¹ ² Кормен, 2013, p. 39—40.
↑ Н. Вирт. Алгоритмы и структуры данных. — М.: ДМК Пресс, 2010. — С. 74. — 272 с. — ISBN 987-5-94074-584-6.
↑ Скиена С. Алгоритмы. Руководство по разработке. — 2-е. — СПб.: БХВ-Петербург, 2014. — С. 137. — 720 с. — ISBN 978-5-9775-0560-4.
↑ ¹ ² Ахо, 2000, p. 237.
↑ Кормен, 2013, p. 47.
↑ Кормен, 2013, p. 48.
↑ Кормен, 2013, p. 48—49.
↑ Кормен, 2013, p. 49.
↑ Кормен, 2013, p. 49—50.
↑ Макконнелл, 2004, p. 74.
↑ Макконнелл, 2004, p. 75.
↑ Макконнелл, 2004, p. 75—76.
↑ Кормен, 2013, p. 51.

Ахо А. В., Хопкрофт Д. Э., Ульман Д. Д. Структуры данных и алгоритмы = Data structures and algorithms / Под ред. А. А. Минько. — М.: Вильямс, 2000. — С. 231. — ISBN 5-8459-0122-7.
Кнут Д. Э. 5.2.1 Сортировка путём вставок // Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с. — ISBN 5-8459-0082-1.
Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. 2.1. Сортировка вставкой // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 3-е изд. — М.: Вильямс, 2013. — С. 38—45. — ISBN 5-8459-1794-8.
Макконнелл Дж. Основы современных алгоритмов = Analysis of Algorithms: An Active Learning Approach / Под ред. С. К. Ландо. — М.: Техносфера, 2004. — С. 72—76. — ISBN 5-94836-005-9.

Реализация сортировки вставками на Pascal и C++
Анимированное представление алгоритма сортировки вставками

[:0-1] ¹ ² Кнут Д. Э. 5.2 Внутренняя сортировка // Искусство программирования. Том 3. Сортировка и поиск = The Art of Computer Programming. Volume 3. Sorting and Searching / под ред. В. Т. Тертышного (гл. 5) и И. В. Красикова (гл. 6). — 2-е изд. — Москва: Вильямс, 2007. — Т. 3. — 832 с. — ISBN 5-8459-0082-1.

[_2a5a5239f7db967b-2] Кормен, 2013, p. 38.

[_2a5a5239f7db967a-3] Кормен, 2013, p. 39.

[_e8e9075ee52eda84-4] ¹ ² Кормен, 2013, p. 39—40.

[5] Н. Вирт. Алгоритмы и структуры данных. — М.: ДМК Пресс, 2010. — С. 74. — 272 с. — ISBN 987-5-94074-584-6.

[6] Скиена С. Алгоритмы. Руководство по разработке. — 2-е. — СПб.: БХВ-Петербург, 2014. — С. 137. — 720 с. — ISBN 978-5-9775-0560-4.

[_515345d9fe527d6d-7] ¹ ² Ахо, 2000, p. 237.

[_2a5a5739f7db9ef5-8] Кормен, 2013, p. 47.

[_2a5a5739f7db9efa-9] Кормен, 2013, p. 48.

[_9cfad72ce798bf0d-10] Кормен, 2013, p. 48—49.

[_2a5a5739f7db9efb-11] Кормен, 2013, p. 49.

[_d37975a8c3393a28-12] Кормен, 2013, p. 49—50.

[_aef1940e6c9f12cb-13] Макконнелл, 2004, p. 74.

[_aef1940e6c9f12ca-14] Макконнелл, 2004, p. 75.

[_ed472b180d215a8b-15] Макконнелл, 2004, p. 75—76.

[_2a5a5839f7dba044-16] Кормен, 2013, p. 51.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

Алгоритмы сортировки
Теория	Сложность О-нотация Отношение порядка Типы сортировки Устойчивая Внутренняя Внешняя
Обменные	Пузырьком Перемешиванием Гномья Быстрая Расчёской Сортировка чёт-нечет Поразрядная
Выбором	Выбором Пирамидальная Плавная
Вставками	Вставками Шелла Деревом
Слиянием	Слиянием
Без сравнений	Подсчётом Блочная
Гибридные	Introsort Timsort
Прочее	Топологическая Сети Битонная
Непрактичные	Bogosort Stooge sort Блинная Медленная

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

Описание

Псевдокод

Анализ алгоритма

Анализ наихудшего случая

Анализ среднего случая

См. также

Примечания

Литература

Ссылки

Дополнительно по теме

Категории