Парная сортировка вставками :: Pairwise Insertion Sort

Оптимизация для сортировки простыми вставками

Оптимизация

В буфер отправляются сразу два (а не один) рядом стоящих элемента.

Сначала метод простой вставки применяется к большему элементу из пары. Затем сразу метод простой вставки применяется к меньшему элементу из пары.

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

Алгоритмическая сложность алгоритма остаётся той же, хотя парные вставки работают несколько быстрее чем обычные.

Характеристики алгоритма

НазваниеПарная сортировка простыми вставками (Pairwise Insertion Sort (binary search))
КлассСортировки вставками
УстойчивостьДа
СравненияДа
Сложность по времениХудшаяO(n2 / 2)
СредняяO(n2 / 4)
ЛучшаяO(n)
Сложность по памятиОбщаяO(n)
ДополнительнаяO(1)

Ссылки

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

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

Insertion sort

Реализация на различных ЯП