Изменения

'''Сортировка вставками''' (англ. ''Insertion sort'') — квадратичный алгоритм [[Сортировка|сортировки]].

<wikitex>Задача заключается в следующем: есть часть массива, которая уже отсортирована, и требуется вставить остальные элементы массива в отсортированную часть, сохранив при этом упорядоченность. Для этого на каждом шаге алгоритма мы выбираем один из элементов входных данных и вставляем его на нужную позицию в уже отсортированной части массива, до тех пор пока весь набор входных данных не будет отсортирован. Метод выбора очередного элемента из исходного массива произволен, однако обычно (и с целью получения устойчивого алгоритма сортировки), элементы вставляются по порядку их появления во входном массиве.

Так как в процессе работы алгоритма могут меняться местами только соседние элементы, каждый обмен уменьшает число [[Таблица инверсий|инверсий]] на единицу. Следовательно, количество обменов равно количеству инверсий в исходном массиве вне зависимости от реализации сортировки. Максимальное количество инверсий содержится в массиве, элементы которого отсортированы по невозрастанию. Число инверсий в таком массиве $<tex>\displaystyle \frac {n(n - 1)} {2}$</tex>.

Алгоритм работает за $<tex>O(n + k)$</tex>, где <tex>k </tex> — число обменов элементов входного массива, равное числу инверсий. В среднем и в худшем случае — за $<tex>O(n^2)$</tex>. Минимальные оценки встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие — когда они расположены в обратном порядке.</wikitex>

InsertionSort'''function''' insertionSort(a): '''for ''' i = 1 '''to ''' n - 1:

'''while (''' j <tex> \geqslant </tex>= 0) '''and (''' a[j] > a[j + 1]):

j = j - 1-

Пример работы алгоритма для массива <tex>[5, 2, 4, 3, 1]</tex>

Так как в среднем количество сравнений для <tex>j</tex>-го элемента равно <tex>j/2</tex>Теперь вместо линейного поиска позиции мы будем использовать [[Целочисленный двоичный поиск | бинарный поиск]], следовательно общее количество сравнений приблизительно изменится с <tex>\frac {O(1+2+3+...+N)}{2} \approx N^2/4</tex>, но это очень много даже при малых <tex>N)</tex>. Суть этого заключается в том, что поиск позиции для вставки <tex>j</tex>-го элемента осуществляется бинарным поиском, вследствие чего количество сравнений для <tex>N</tex> элементов до <tex>O(N \cdot \log_{2} log N) </tex>. Количество сравнений заметно уменьшилось, но для того, чтобы поставить <tex>R_j</tex> элемент на <tex>i</tex>-тое своё место, всё ещё необходимо переместить <tex>j-i</tex> большое количество элементов. В итоге время выполнения алгоритма в асимптотически не уменьшилось . Бинарные вставки выгодно использовать только в среднем в четыре раза : <tex>C \cdot N \cdot (N/4+log_{2} N) \approx N^2/4</tex>, следовательно <tex>C=1/4</tex>случае когда сравнение занимает много времени по сравнению со сдвигом. Например когда мы используем массив длинных чисел. InsertionSort'''function''' insertionSort(a): '''for ''' i = 1 '''to ''' n - 1:

k = BinSearchbinSearch(a, a[i], 0, j) '''for''' m = j '''downto''' k swap(a[km], a[im+1])

Суть этого метода в том, что вместо отсортированной части массива мы используем область вывода. Первый элемент помещается в середину области вывода, а место для последующих элементов освобождается потём путём сдвига элементов влево или вправо туда, куда выгоднее.Пример для набора элементов 5 7 3 4 6 5 5 7 3 5 7 3 4 5 7 3 4 5 6 7 Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Время выполнения алгоритма сократилось в восемь раз : <tex>C \cdot N \cdot (N/8+log_{2} N) \approx N^2/8</tex>[ 5, следовательно <tex>C=1/8</tex>. === Метод Шелла ===Метод Шелла основан на том7, что сортировка вставками более эффективна на маленьких или на частичной отсортированных входных данных. Устройство метода Шелла более понятно если рассматривать его на фиксированном наборе данных. Например мы имеем набор из 16 элементов <tex>R_1...R_{16}</tex> разобьём их на пары <tex>(R_1,R_9),...,(R_83,R_{16})</tex>. Каждое разделение называется проходом. Отсортируем каждую из пар. Разобьем на группы по 4 элемента <tex>(R_1,R_5,R_9,R_{13}),...,(R_4,R_8,R_{12},R_{16})6 ]</tex>. Отсортируем каждую из пар. Разобьём на 2 группы по восемь элементов <tex>(R_1,R_3,R_5,R_7,R_9,R_ {11},R_{13},R_{15}),(R_2,R_4,R_6,R_8,R_{10},R_{12},R_{14},R_{16})</tex>. Отсортируем каждую из пар. При четвёртоми последнем проходе сортируются все 16 элементов. В итоге получится отсортированный массив| style="background-color:#CCC;margin:0.5px"Последовательность смещений 1 2 4 8 может меняться в зависимости от неё меняется и асимптотика. Например предложенная Хиббардом последовательность <tex>2^i!style="background-1 \le N, i \in N </tex> приводит к алгоритму с асимптотиткой <tex> O(N^{3/2}) </tex>.color:#EEE"| До!style="background-color:#EEE"| После!style="background-color:#EEE"| Описание шага|-|colspan==Вставка в список ===При этой сортировке мы используем односвязной список вместо упорядоченной части массива. Теперь на не потребуется времени на сдвиг, а понадобиться всего лишь изменить родственные связи. При этом время выполнения сокращается в четыре раза : <tex>C \cdot N \cdot 3|''Первый проход (N/4+2проталкиваем первый элемент — '''''5''''') \approx N^2/4</tex>, следовательно <tex>C=1/4</tex>.''|-|style="background-color:#FFF;padding:2px 10px"| |style="background-color:#FFF;padding:2px 30px"| '''5'''|style= Сортировка с вычислением адреса ===Сортировку с вычисление адреса выгодно использовать когда ключи распределены равномерно и не скапливаются хаотично "background-color:#FFF;padding:2px 10px"| Так как в отдельных диапазонах значений. Вместо левой отсортированной части массива поле вывода нет элементов, то мы будем использовать <tex> M </tex> односвязных списков, в каждом из которых будут храниться значения из определённого диапазонапросто добавляем элемент туда. С каждым списком работаем как при простых выставках в список. Вероятность того что элемент попадёт в какой|-либо список <tex>1/M</tex>, следовательно для каждого элемента происходит примерно <tex> \frac {N} {4 \cdot M} </tex> сравнений, следовательно общее количество сравнений <tex> \frac {N^2} {4 \cdot M} </tex>, а при <tex>M</tex> порядка <tex>N</tex> асимптотическая сложность уменьшается до <tex>O|colspan=3|''Второй проход (Nпроталкиваем второй элемент — '''''7''''')</tex>.''Рассмотрим на примере.|-Входные данные |style="background-color:#FFF;padding: 867 345 984 245 123 743 550 490 300 2px 30px"| 5 Будем использовать 4 списка с соответствующими диапазонами значений |style="background-color:#FFF;padding: 0 2px 30px"| 5 '''7'''|style="background- 250color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и, 251 - 500так как позиция крайняя, 501 - 750, 751- 1000то сдвигать ничего не приходится.{|border="1"- | colspan=3|''Третий проход (проталкиваем третий — '''''3 элемента''''')'' |6 элементов- |9 элементовstyle="background-color:#FFF;padding:2px 30px"| 5 7 |style="background-color:#FFF;padding:2px 20px"| '''3''' 5 7 |0 style="background- 250color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и, так как позиция крайняя, то сдвигать ничего не приходится. |- |123 245 colspan=3|123 245''Четвертый проход (проталкиваем четвертый элемент — '''''4''''')'' |- |251 style="background- 500 color:#FFF;padding:2px 20px"|3453 5 7 |345 style="background-color:#FFF;padding:2px 10px"|300 345 4903 '''4''' 5 7 |style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию. Расстояние до левого края зоны вывода меньше, чем до правого, значит сдвигаем левую часть. |501 - 750 | colspan=3|743''Четвертый проход (проталкиваем пятый элемент — '''''6''''')'' |550 743- |style="background-color:#FFF;padding:2px 10px"| 3 4 5 7 |751 style="background- 1000 color:#FFF;padding:2px 10px"|867 9843 4 5 '''6''' 7 |867 984 style="background-color:#FFF;padding:2px 10px"|867 984Расстояние до правого края меньше чем до левого, следовательно двигаем правую часть. |}  == Сложность ==Так как алгоритм сравнивает Как можно заметить структура поля вывода имеет сходство с [[Персистентный дек| деком]], а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и меняет местами соседние элементы пока не найдёт подходящую позициюдвигаем его. Как мы видим в этом примере понадобилось сдвинуть всего <tex>3</tex> элемента. Благодаря тому что для вставки <tex>j</tex>-ого элемента потребуется <tex>j/2</tex> сдвигов в худшем случае вместо <tex>j</tex>, то худший случай будет при входных данных отсортированных и итоговое число необходимых операций в обратном порядкехудшем случае составит <tex>N^2 / 4 + N \log N</tex>.

* [[Сортировка Шелла]]== Источники информации==* [http://ru.wikipedia.org/wiki/Сортировка_вставками %D0%A1%D0%BE%D1%80%D1%82%D0%B8%D1%80%D0%BE%D0%B2%D0%BA%D0%B0_%D0%B2%D1%81%D1%82%D0%B0%D0%B2%D0%BA%D0%B0%D0%BC%D0%B8 Сортировка вставками — Википедия]* Н. Вирт «Алгоритмы '''Алгоритмы и структуры данных»данных''' {{---}} Невский Диалект, часть 22008.2{{---}} 352 с.1 "Сортировка с помощью прямого включения"== Дополнительные материалы =={{---}} ISBN 978-5-7940-0065-8