Сортировки массивов. Шейкерная сортировка

Задача сортировки

Задача сорт заключаются в упорядочении элементов массива.

 

Шейкерная сортировка широко используется в тех случаях, когда известно, что элементы почти упорядочены

Шейкер сортировка принимает во внимания тот факт, что от последней перестановки до конца (начала) массива находятся отсортированные элементы. Учитывая данный факт, просмотр осуществляется не до конца (начала) массива, а до конкретной позиции. Поэтому при использовании Шейкер сортировки необходимо запоминать индекс последней перестановки. На следующем шаге цикла начнём просмотр с последней перестановки. Просмотр массива осуществляется слева направо (устанавливается правая граница). Затем справа налево (устанавливается левая граница). Просмотр массива осуществляется до тех пор, пока все элементы не встанут в порядке возрастания (убывания).

Предположим, мы упорядочиваем массив в порядке возрастания. После первого прохода "Пузырьком", самый большой элемент массива встанет на свое место. Выполним второй проход наоборот, от предпоследнего элемента до первого. После этого прохода встанет на свое место самый маленький элемент. Так и будем выполнять наши проходы массива: нечетные слева - направо и четные справа - налево. При этом на нечетных проходах будет занимать свое место самый большой элемент (из оставшихся), а при нечетных самый маленький (также из оставшихся).

Сравниваем 33 с 7. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,33,15,11,0,4,25,-1.
Сравниваем 33 с 15. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,33,11,0,4,25,-1.
Сравниваем 33 с 11. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,11,33,0,4,25,-1.
Сравниваем 33 с 0. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,11,0,33,4,25,-1 и т.д.
Сравниваем 33 с -1. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,11,0,4,25,-1,33. Затем меняем направление просмотра и продолжаем процесс.
Сравниваем 25 с -1.. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,11,0,4,-1,25,33.
Сравниваем 4 с -1.. Меняем местами элементы и сохраняем позицию перестановки. Массив равен 7,15,11,0,-1,4,25,33 и т.д.
Сравниваем 7 с -1.. Меняем местами элементы и сохраняем позицию перестановки. Массив равен -1,7,15,11,0,4,25,33. В итоге получаем после первого шага Шейкер сортировки (рис. 1).

Запоминать, были или не были перестановки в процессе некоторого прохода.

Запоминать не только сам факт, что обмен имел место, но и положение (индекс) последнего обмена.

Чередовать направление последовательных просмотров.

Левая граница = Номер первого элемента

Правая граница = Номер последнего элемента

Пока Левая граница < Правой границы делать

Прямой проход "Пузырька" от Левой границы до Правой-1

Правая граница = Правая граница - 1

Обратный проход "Пузырька" от Правой границы до Левой+1

Левая граница = Левая граница + 1

 

k:= 25; {Индекс последнего изменения}

s:= 1; {Первый элемент массива}

e:= 25; {Последний элемент массива}

while e > s do

Begin

for i:= e downto s+1 do if A [i] < A[i-1] then

Begin

tmp:= A[i];

A[i]:= A[i-1];

A[i-1]:= tmp;

k:= i; {запоминание индекса последней перестановки}

end;

s:=k;

for i:= s to e-1 do if A[i]>A[i+1] then

Begin

tmp:= A[i];

A[i]:= A[i+1];

A[i+1]:= tmp;

k:= i;

end;

e:=k;

end;

 

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

Задача сортировки

Задача сорт заключаются в упорядочении элементов массива.

Эта сортировка⁹⁾ базируется на уже известном нам алгоритме простых вставок ПрВст. Смысл ее состоит в раздельной сортировке методом ПрВст нескольких частей, на которые разбивается исходный массив. Эти разбиения помогают сократить количество пересылок: для того, чтобы освободить "правильное" место для очередного элемента, приходится уже сдвигать меньшее количество элементов.

Алгоритм УлШелл

На каждом шаге (пусть переменная t хранит номер этого шага) нужно произвести следующие действия:

1. вычленить все подпоследовательности, расстояние между элементами которых составляет k_t;
2. каждую из этих подпоследовательностей отсортировать методом ПрВст.

Нахождение убывающей последовательности расстояний k_t, k_t-1..., k₁ составляет главную проблему этого алгоритма. Многочисленные исследования позволили выявить ее обязательные свойства:

• k₁ = 1;
• для всех t k_t > k_t-1;
• желательно также, чтобы все k_t не были кратными друг другу (для того, чтобы не повторялась обработка ранее отсортированных элементов).

Дональд Кнут предлагает две "хорошие" последовательности расстояний:

1, 4, 13, 40, 121, _ (k_t = 1+3*k_t-1)

1, 3, 7, 15, 31, _ (k_t = 1+2*k_t-1 = 2^t -1)

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

Как же определить начальное значение для t (а вместе с ним, естественно, и для k_t)?

Можно, конечно, шаг за шагом проверять, возможно ли вычленить из сортируемого массива подпоследовательность (хотя бы длины 2) с расстояниями 1, 3, 7, 15 и т.д. между ее элементами. Однако такой способ довольно неэффективен. Мы поступим иначе, ведь у нас есть формула для вычисления k_t = 2^t -1.

Итак, длина нашего массива (N) должна попадать в такие границы:

k_t <= N -1 < k_t+1

или, что то же самое,

2^t <= N < 2^t+1

Прологарифмируем эти неравенства (по основанию 2):

t <= log N < t+1

Таким образом, стало ясно, что t можно вычислить по следующей формуле:

t = trunc(log N))

К сожалению, язык Pascal предоставляет возможность логарифмировать только по основанию е (натуральный логарифм). Поэтому нам придется вспомнить знакомое из курса средней школы правило "превращения" логарифмов:

log_mx =log_zx/log_zm

В нашем случае m = 2, z = e. Таким образом, для начального t получаем:

t:= trunc(ln(N)/ln(2)).

Однако при таком t часть подпоследовательностей будет иметь длину 2, а часть - и вовсе 1. Сортировать такие подпоследовательности незачем, поэтому стоит сразу же отступить еще на 1 шаг:

t:= trunc(ln(N)/ln(2))-1

Расстояние между элементами в любой подпоследовательности вычисляется так:

k:= (1 shl t)-1; {k= 2^t-1}

Количество подпоследовательностей будет равно в точности k. В самом деле, каждый из первых k элементов служит началом для очередной подпоследовательности. А дальше, начиная с (k+1)-го, все элементы уже являются членами некоторой, ранее появившейся подпоследовательности, значит, никакая новая подпоследовательность не сможет начаться в середине массива.

Сколько же элементов будет входить в каждую подпоследовательность? Ответ таков: если длину всей сортируемой последовательности (N) можно разделить на шаг k без остатка, тогда все подпоследовательности будут иметь одинаковую длину, а именно:

s:= N div k;

Если же N не делится на шаг k нацело, то первые р подпоследовательностей будут длиннее на 1. Количество таких "удлиненных" подпоследовательностей совпадает с длиной "хвоста" - остатка от деления N на шаг k:

P:= N mod k;