Шейкерная сортировка ShakerSort

элементы «всплывают» быстро, а «тяжелые» «тонут» медленно.
Пример. СИДОРОВ

ВО
ВР
ВО
ВД
ВИ
ВСИДОРО

для уменьшения трудоемкости:

1) Изменение направления просмотра массива на каждой

итерации.
2) Установление границ рабочей части массива на место последнего обмена на каждой итерации.

границы рабочей части массива,
n – количество элементов в массиве.
 
L :=

1, R := n, k := n,
DO
DO ( j := R, R-1, ... L+1)
IF (aj < aj-1) aj↔aj-1, k := j FI
OD
L := k
DO ( j := L, L+1, ... R-1)
IF (aj > aj+1) aj↔aj+1, k := j FI
OD
R := k
OD (L < R)

П О В

А
А В
А О
А П
А А
А Р
А У
А К
А К У Р А П О В
К У
Р У
А У
П У
О У
В У
А К Р А П О В У
В О
В П
А В
А Р
А К

А А К Р В П О У
К Р
В Р
П Р
О Р
А А К В П О Р У
О П
В О
В К
А А В К О П Р У
К О
О П
А А В К О П Р У

элемент массива и включаем его на нужное место среди первых

(i-1) элементов, при этом все элементы, которые больше ai сдвигаются на одну позицию вправо.

DO ( i: = 2, 3, …,

n )
t := ai, j := i -1
DO ( j > 0 и t < aj )
aj+1 := aj
j := j -1
OD
aj+1 := t
OD

О В А
К У Р

А П О В А
К Р У А П О В А
А К Р У П О В А
А К П Р У О В А
А К О П Р У В А
А В К О П Р У А
А А В К О П Р У

видно, что, чем лучше упорядочен массив, тем меньше операций потребуется

для его сортировки.
Основная идея метода Шелла ShellSort состоит в предварительном улучшении порядка элементов массива, а затем окончательной сортировке его методом прямого включения.
Шелл предложил работать в методе прямого включения с шагом k большим, чем 1, что предварительно улучшило бы упорядоченность массива.
Чем больше величина шага, тем меньше операций сравнения и пересылки приходиться выполнять.

> 1 называется к - сортировкой.
Метод Шелла заключается в

проведении сначала нескольких к-сортировок, а затем окончательной сортировке массива с шагом к=1.
Обозначим
H = ( h1 , h2 , … , hm ) – последовательность из m возрастающих шагов, где h1 = 1, h1 < h2 < h3 < …< hm .
Производя последовательно к-сортировки с шагами hm , hm-1 ,.., h1 , получим упорядоченный массив. Это гарантируется тем, что последний шаг h1 = 1.

DO ( k := hm , hm-1 , … 1 )
DO ( i := k+1, k+2, … n )
t := ai , j := i - k
DO ( j > 0 и t < aj )
aj+k := aj
j := j - k
OD
aj+k := t
OD
OD

О В А
К У Р

А П О В А
К А Р У П О В А
К А П У Р О В А
К А П О Р У В А
В А К О П У Р А
В А К А П О Р У

О Р У
А В К

А П О Р У
А В К А П О Р У
А А В К П О Р У
А А В К П О Р У
А А В К О П Р У
А А В К О П Р У

O ( n1.2 ) , n→∞.
Метод Шелла существенно быстрее

методов с квадратичной трудоемкостью.
В примере: Insert – 46 операций,
Shell – 34 операции.
Метод Шелла не устойчив.
Метод зависит от исходной упорядоченности массива.