Материал: АиСД. Практикум (in dev)

4. Сортировка Шелла

В методе Шелла сравниваются не соседние элементы, а элементы, расположенные на расстоянии d (где d – шаг между сравниваемыми элементами) d = [n/2]. После каждого просмотра шаг d уменьшается вдвое. На последнем просмотре он сокращается до d = 1.

Например, пусть дан список, в котором число элементов чётно:

{40, 11, 83, 57, 32, 21, 75, 64}

Список длины n разбивается на n/2 частей, т.е. d = [n/2] = 4.

Исходный массив	40	11	83	57	32	21	75	64
d = 4	32	11	75	57	40	21	83	64
Полученный массив	32	11	75	57	40	21	83	64

Рис. 5. Метод Шелла (d=4 )

Исходный массив	32	11	75	57	40	21	83	64
d = 2	32	11	75 40	57 21	75 75	57 57	83	64
Полученный массив	32	11	40	21	75	57	83	64

Рис. 6. Метод Шелла (d=2 )

При первом просмотре сравниваются элементы, отстоящие друг от друга на d = 4 (рис.5), т.е. k₁ и k₅, k₂ и k₆ и т.д. Если k_i > k_i+d, то происходит обмен между позициями i и (i+d). Перед вторым просмотром выбирается шаг d = [d / 2] = 2 ( рис.6 ). Затем выбираем шаг d = [d / 2] = 1 ( рис.7 ), т.е. имеем аналогию с методом стандартного обмена.

Сложность метода Шелла O(0,3n(log₂n)²).

Исходный список	32	11	40	21	75	57	83	64
d =1	11	32 32	40 21	40 40	75 57	75 75	83 64	83
Полученный список	11	32	21	40	57	75	64

Рис. 7. Метод Шелла (d=1 )

5. Быстрая сортировка (сортировка Хоара)

В методе быстрой сортировки фиксируется какой-либо ключ (базовый), относительно которого все элементы с большим весом перебрасываются вправо, а с меньшим – влево. При этом весь список элементов делится относительно базового ключа на две части. Для каждой части процесс повторяется.

Поясним метод на примере.

На рис.8 представлен первый этап быстрой сортировки. В первой строке указана исходная последовательность.

Примем первый элемент последовательности за базовый ключ, выделим его квадратом и обозначим k₀ = 40. Установим два указателя : i и j, из которых i начинает отсчёт слева (i=1), а j – справа (j=n).

Сравниваем базовый ключ k₀ и текущий ключ k_j. Если k₀<=k_j, то устанавливаем j=j-1 и проводим следующее сравнение k₀ и k_j. Продолжаем уменьшать j до тех пор, пока не достигнем условия k₀>k_J. После этого меняем местами ключи k₀ и k_j (шаг 3 на рис.8 ).

6. Сортировка в нелинейных структурах

Сортировка в нелинейных структурах осуществляется только на бинарных деревьях (деревьях, из каждой вершины которого выходит по два ребра).

1. Турнирная сортировка

Свое название эта сортировка получила, потому что она используется при проведении соревнований, турниров и олимпиад. Элементы исходного множества представляются листьями дерева. Их по парное сравнение позволяет определить максимальный элемент.

Пример: Дано исходное множество { 7, 1, 9, 3, 6, 5, 8 }

Производится по парное сравнение элементов снизу- вверх. Найденный максимальный элемент помещается в результирующее множество.

В результате будет получено упорядоченное множество { 9,8,7,6,5,3}

2. Пирамидальная сортировка

Данный тип сортировки заключается в построение пирамидального дерева.

Пирамидальное дерево – это бинарное дерево обладающее тремя свойствами:

• В вершине каждой триады располагается элемент с большим весом.

• Листья бинарного дерева располагаются либо в одном уровне либо в двух соседних

на одном уровне на соседних

уровнях