Изменения

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

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

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

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

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

k = '''BinSearch'''(a, a[i], 0, j) '''swap'''(a[k], a[i])

Пример для набора элементов <tex>5 , 7 , 3 , 4 , 6 </tex> {| style="background-color:#CCC;margin:0.5px"!style="background-color:#EEE"| До!style="background-color:#EEE"| После!style="background-color:#EEE"| Описание шага|-|colspan=3|''Первый проход (проталкиваем второй элемент — '''''5''''')''|-|style="background-color:#FFF;padding:2px 10px"| |style="background-color:#FFF;padding:2px 10px"| '''5'''|style="background-color:#FFF;padding:2px 10px"| Так как в поле вывода нет элементов то мы просто добавляем элемент туда.|-|colspan=3|''Второй проход (проталкиваем третий элемент — '''''7''''')'' |-|style="background-color:#FFF;padding:2px 10px"| 5 |style="background-color:#FFF;padding:2px 10px"| 5 '''7'''|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и так как позиция крайняя то сдвигать ничего не приходится.|- |colspan=3|''Третий проход (проталкиваем четвертый — '''''3''''')''|-|style="background-color:#FFF;padding:2px 10px"| 5 7|style="background-color:#FFF;padding:2px 10px"| '''3''' 5 7|style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию и так как позиция крайняя то сдвигать ничего не приходится.|-|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''4''''')''|-|style="background-color:#FFF;padding:2px 10px"| 3 5 7 |style="background-color:#FFF;padding:2px 10px"| 3 '''4''' 5 7 |style="background-color:#FFF;padding:2px 10px"| С помощью Бинарного поиска находим позицию. Расстояние до левого края зоны вывода меньше ем до правого то сдвигаем левую часть.|-|colspan=3|''Четвертый проход (проталкиваем пятый элемент — '''''6''''')''|-|style="background-color:#FFF;padding:2px 10px"| 3 4 5 7 |style="background-color:#FFF;padding:2px 10px"| 3 4 5 '''6 ''' 7 |style="background-color:#FFF;padding:2px 10px"| Расстояние до правого края меньше чем до левого, следовательно двигаем правую часть.|} Как можно заметить структура поля вывода имеет сходство с Двусвязной очередью, а именно мы выбираем край к которому ближе наш элемент, затем добавляем с этой стороны наш элемент и двигаем его. Как мы видим в этом примере понадобилось сдвинуть всего 3 элемента. Время выполнения алгоритма сократилось в восемь раз , благодаря тому что теперь мы вместо перемещения в среднем <tex>N/2</tex> мы перемещаем <tex>N/4</tex> элементов : <tex>O(C \cdot N \cdot (N/8+log_{2} \log N) \approx ) = O(N^2/8)</tex>, следовательно <tex>C=1/8</tex>.

При этой сортировке мы используем односвязной список вместо упорядоченной части массива. Теперь на не потребуется времени на сдвиг, а понадобиться всего лишь изменить родственные связи. При этом время выполнения сокращается в четыре раза : <tex>O(C \cdot N \cdot (N/4+2) \approx ) = O( N^2/4)</tex>, следовательно <tex>C=1/4</tex>.

Сортировку с вычисление адреса выгодно использовать когда ключи распределены равномерно и не скапливаются хаотично в отдельных диапазонах значений. Вместо левой отсортированной части массива мы будем использовать <tex> M </tex> односвязных списков, в каждом из которых будут храниться значения из определённого диапазона. С каждым списком работаем как при простых выставках в список. Вероятность того что элемент попадёт в какой-либо список <tex>1/M</tex>, следовательно для каждого элемента происходит примерно <tex> \displaystyle \frac {N} {4 \cdot M} </tex> сравнений, следовательно общее количество сравнений <tex> \displaystyle \frac {N^2} {4 \cdot M} </tex>, а при <tex>M</tex> порядка <tex>N</tex> асимптотическая сложность уменьшается до <tex>O(N)</tex>.

Входные данные : <tex>867 , 345 , 984 , 245 , 123 , 743 , 550 , 490 , 300 </tex> Будем использовать 4 списка с соответствующими диапазонами значений : <tex>0 - 250, 251 - 500, 501 - 750, 751- 1000</tex>.