imported>Железный капут: Бот: откат правок 81.23.202.156 по запросу MBH

2025-09-20T14:55:10Z

Бот: откат правок 81.23.202.156 по запросу MBH

Новая страница

{{Алгоритм
| предназначение = [[Алгоритм сортировки]]
| изображение = Insertion-sort-example-300px.gif
| подпись = Пример сортировки вставками
| данные = [[Массив (программирование)|Массив]]
| время = <math>O(n^2)</math> сравнений, обменов
| лучшее-время = <math>O(n)</math> сравнений, 0 обменов
| среднее-время = <math>O(n^2)</math> сравнений, обменов
| память = <math>O(n)</math> всего, <math>O(1)</math> вспомогательный
}}
'''Сортировка вставками''' ({{lang-en|Insertion sort}}) — [[алгоритм сортировки]], в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов<ref>{{Книга:Кнут|3|часть=5.2 Внутренняя сортировка|ref=Кнут}}</ref>. [[Вычислительная сложность]] — <math>O(n^2)</math>.

== Описание ==
[[Файл:Dsa ins sort.png|thumb|left|400px|Пример сортировки вставками]]
На вход алгоритма подаётся последовательность <math>n</math> чисел: <math>a_1, a_2, ..., a_n</math>. Сортируемые числа также называют ''ключами''. Входная последовательность на практике представляется в виде массива с <math>n</math> элементами. На выходе алгоритм должен вернуть перестановку исходной последовательности <math>a_{1}^{'}, a_{2}^{'}, ..., a_{n}^{'}</math>, чтобы выполнялось следующее соотношение <math>a_{1}^{'} \leqslant a_{2}^{'} \leqslant ... \leqslant a_{n}^{'}</math>{{sfn|Кормен|2013|p=38}}.

В начальный момент отсортированная последовательность пуста. На каждом шаге алгоритма выбирается один из элементов входных данных и помещается на нужную позицию в уже отсортированной последовательности до тех пор, пока набор входных данных не будет исчерпан. В любой момент времени в отсортированной последовательности элементы удовлетворяют требованиям к выходным данным алгоритма{{sfn|Кормен|2013|p=39}}.

Данный алгоритм можно ускорить при помощи использования бинарного поиска для нахождения места текущему элементу в отсортированной части. Проблема с долгим сдвигом массива вправо решается при помощи смены указателей<ref>{{Книга:Кнут|3|часть=5.2.1 Сортировка путём вставок|ref=Кнут}}</ref>.

== Псевдокод ==
На вход процедуре сортировки подаётся массив <math>A[1..n]</math>, состоящий из элементов последовательности <math>A[1], A[2], ..., A[n]</math>, которые требуется отсортировать. <math>n</math> соответствует <math>A.\mathrm{length}</math> — размеру исходного массива. Для сортировки не требуется привлечения дополнительной памяти, кроме постоянной величины для одного элемента, так как выполняется перестановка в пределах массива. В результате работы процедуры во входном массиве оказывается требуемая выходная последовательность элементов{{sfn|Кормен|2013|p=39—40}}.

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

{|
|-
|
'''for''' j = 2 '''to''' A.length '''do'''
key = A[j]
i = j-1
'''while''' (i > 0 and A[i] > key) '''do'''
A[i + 1] = A[i]
i = i - 1
'''end while'''
A[i+1] = key
'''end '''{{sfn|Кормен|2013|p=39—40}}
|
'''for''' i = 2 '''to''' n '''do'''
x = A[i]
j = i
'''while''' (j > 1 and A[j-1] > x) '''do'''
A[j] = A[j-1]
j = j - 1
'''end while'''
A[j] = x
'''end for'''<ref>{{Книга|автор=Н. Вирт|заглавие=Алгоритмы и структуры данных|ответственный=|издание=|место=М.|издательство=ДМК Пресс|год=2010|страницы=74|страниц=272|isbn=987-5-94074-584-6}}</ref>
|
A[0] = -<math>\infty</math>
'''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'''<ref>{{Книга|автор=Скиена С.|заглавие=Алгоритмы. Руководство по разработке|ссылка=https://archive.org/details/algoritmyrukovod0000unse/page/137|ответственный=|издание=2-е|место=СПб.|издательство=БХВ-Петербург|год=2014|страницы=137|страниц=720|isbn=978-5-9775-0560-4}}</ref>{{sfn|Ахо|2000|p=237}}
|}
В последнем варианте обмен <code>x = A[j]; A[j] = A[j-1]; A[j-1] = x</code> представлен операцией swap из-за чего он немного медленнее. Значение введённого А[0] меньше любого значения остальных элементов{{sfn|Ахо|2000|p=237}}.

== Анализ алгоритма ==
Время выполнения алгоритма зависит от входных данных: чем большее множество нужно отсортировать, тем большее время потребуется для выполнения сортировки. Также на время выполнения влияет исходная упорядоченность массива. Время работы алгоритма для различных входных данных одинакового размера зависит от элементарных операций, или шагов, которые потребуется выполнить{{sfn|Кормен|2013|p=47}}.

Для каждой инструкции алгоритма введём временную стоимость и количество повторений, где <math>t_j</math> — количество проверок условия во внутреннем цикле ''while''{{sfn|Кормен|2013|p=48}}:
{| class="wikitable" border="1" width="80%"
|-
!width="40%"|Код
!width="15%"|Стоимость
!width="25%"|Повторы
|-
|for j = 2 to A.length
|<math>c_1</math>
|<math>n</math>
|-
|key = A[j]
|<math>c_2</math>
|<math>n-1</math>
|-
|i = j — 1
|<math>c_3</math>
|<math>n-1</math>
|-
|while i > 0 and A[i] > key
|<math>c_4</math>
|<math>\sum_{j=2}^n t_j</math>
|-
|A[i+1] = A[i]
|<math>c_5</math>
|<math>\sum_{j=2}^n (t_j-1)</math>
|-
|i = i — 1
|<math>c_6</math>
|<math>\sum_{j=2}^n (t_j-1)</math>
|-
|A[i+1] = key
|<math>c_7</math>
|<math>n-1</math>
|}

Время работы алгоритма сортировки вставками — это сумма времён работы каждого шага{{sfn|Кормен|2013|p=48—49}}: <math>T(n)=c_1n+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)</math>.

Самым благоприятным случаем является отсортированный массив. При этом все внутренние циклы состоят всего из одной итерации, то есть <math>t_j=1</math> для всех <math>j</math>. Тогда время работы алгоритма составит <math>T(n)=(c_1+c_2+c_3+c_4+c_7)n-(c_2+c_3+c_4+c_7)=O(n)</math>. Время работы линейно зависит от размера входных данных{{sfn|Кормен|2013|p=49}}.

=== Анализ наихудшего случая ===
Наихудшим случаем является массив, отсортированный в порядке, обратном нужному. При этом каждый новый элемент сравнивается со всеми в отсортированной последовательности. Это означает, что все внутренние циклы состоят из j итераций, то есть <math>t_j=j</math> для всех <math>j</math>. Тогда время работы алгоритма составит:

<math>T(n)=c_1n+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)</math>

<math>T(n)=c_1n+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)</math>.

Время работы является квадратичной функцией от размера входных данных{{sfn|Кормен|2013|p=49—50}}.

=== Анализ среднего случая ===
Для анализа среднего случая нужно посчитать среднее число сравнений, необходимых для определения положения очередного элемента. При добавлении нового элемента потребуется, как минимум, одно сравнение, даже если этот элемент оказался в правильной позиции. <math>i</math>-й добавляемый элемент может занимать одно из <math>i+1</math> положений. Предполагая случайные входные данные, новый элемент равновероятно может оказаться в любой позиции{{sfn|Макконнелл|2004|p=74}}. Среднее число сравнений для вставки <math>i</math>-го элемента{{sfn|Макконнелл|2004|p=75}}:

<math>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}</math>

Для оценки среднего времени работы для <math>n</math> элементов нужно просуммировать{{sfn|Макконнелл|2004|p=75—76}}:

<math>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)</math>

<math>T(n)\approx\frac{n^2-n}{4}+(n-1)-(\ln(n)-1)=O(n^2)</math>

Временная [[сложность алгоритма]] — <math>O(n^2)</math>. Однако, из-за константных множителей и членов более низкого порядка алгоритм с более высоким порядком роста может выполняться для небольших входных данных быстрее, чем алгоритм с более низким порядком роста{{sfn|Кормен|2013|p=51}}.

== См. также ==
* [[Алгоритм сортировки#Список алгоритмов сортировки|Список алгоритмов сортировки]]
* [[Сортировка пузырьком]]
* [[Сортировка выбором]]
* [[Гномья сортировка]]

== Примечания ==
{{примечания|3}}

== Литература ==
* {{Книга:Ахо. Структуры данных и алгоритмы|страницы=231|ref=Ахо}}
* {{Книга:Кнут|3|часть=5.2.1 Сортировка путём вставок|ref=Кнут}}
* {{Книга:CLRS|2013|часть=2.1. Сортировка вставкой|страницы=38—45|ref=Кормен}}
* {{Книга:Основы современных алгоритмов|страницы=72—76|ref=Макконнелл}}

== Ссылки ==
{{wikibooks|Примеры реализации сортировки вставками|Примеры реализации сортировки вставками}}
* [http://algolist.manual.ru/sort/insert_sort.php Сортировка вставками]
* [http://kvodo.ru/sortirovka-vstavkami-2.html Реализация сортировки вставками на Pascal и C++]
* [http://www.sorting-algorithms.com/insertion-sort Анимированное представление алгоритма сортировки вставками]

{{Алгоритмы сортировки}}

[[Категория:Алгоритмы сортировки]]

Сортировка вставками - История изменений

imported>Железный капут: Бот: откат правок 81.23.202.156 по запросу MBH