ГЛАВА 1. Алгоритмы сортировок

1.1 Сортировка методом обмена

Алгоритм сортировки обменами основывается на сравнении и смене мест для пары соседних элементов и продолжении этого процесса до тех пор, пока не будут упорядочены все элементы.

Мы повторяем проходы по массиву, сдвигая каждый раз наименьший элемент оставшейся последовательности к левому концу массива. Если мы будем рассматривать массивы как вертикальные, а не горизонтальные построения, то элементы можно интерпретировать как пузырьки в чане с водой, причём вес каждого соответствует его ключу. В этом случае при каждом проходе один пузырек как бы поднимается до уровня, соответствующего его весу(см. табл. 1). Такой метод широко известен под именем «пузырьковая сортировка». В своем простейшем виде он представлен в программе 1.

Таблица 1.

Пример пузырьковой сортировки

Программа 1. Процедура ExchangeSort

procedure ExchangeSort(var A: mas);

var

x: integer;

begin

for i: = N downto 2 do

for j: = 2 to i do

if A[j] < A[j - 1] then

begin

x: = A[j];

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

A[j - 1]: = x;

end;

end;

1.2 Сортировка с помощью выбора

Этот прием основан на следующих принципах:

1. Выбираем элемент с наименьшим ключом.

2. Передвигаем на 1 позицию направо элементы, больше выбранного элемента.

3. Вставляем выбранный элемент в нужную позицию.

4. Затем этот процесс повторяется с оставшимися n-1 элементами, n-2 элементами и т.д. до тех пор, пока не останется один, самый большой элемент.

Процесс работы этого метода приведен в таблице 2. Реализация этого алгоритма в программе 2.

Таблица 2.

Пример сортировки вставками

Программа 2. Процедура InsertSort

procedure InsertSort(var A: mas);

var

i, k: Integer;

x: integer;

begin

for i: = 2 to N do

begin

k: = i;

x: = A[i];

while (A[k - 1] > x) do

begin

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

k: = k - 1;

end;

A[k]: = x;

end;

end;

1.3 Сортировка методом Хоара

Ч. Хоар изобрел алгоритм сортировки массива и назвал его метод быстрой сортировки(Quicksort).

В Quicksort исходят из того соображения, что для достижения наилучшей Эффективности сначала лучше производить перестановки на большие расстояния. Предположим, у нас есть n элементов, расположенных по ключам в обратном порядке. Их можно отсортировать за n/2 обменов, сначала поменять местами самый левый с самым правым, а затем последовательно двигаться с двух сторон. Конечно, это возможно только в том случае, когда мы знаем, что порядок действительно обратный. Но из этого примера можно извлечь нечто действительно поучительное.

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

Программа 3. Функция Partition

function Partition(var A: mas; l, r: Integer; x: integer): Integer;

var

i, j: Integer;

t: integer;

begin

i: = l - 1;

j: = r + 1;

repeat

repeat

j: = j - 1;

until x > = A[j];

repeat

i: = i + 1;

until A[i] > = x;

if i < j then

begin

t: = A[i];

A[i]: = A[j];

A[j]: = t;

end;

until i > = j;

Partition: = j;

end;

Наша цель – не только провести разделение на части исходного массива элементов, но и отсортировать его. Сортировку от разделения отделяет, однако, лишь небольшой шаг: нужно применить этот процесс к получившимся двум частям, затем к частям, затем к частям частей, и так до тех пор, пока каждая их частей не будет состоять из одного-единственного элемента. Эти действия описываются программой 4.

Программа 4. Процедура RecoursiveQuicksort

procedure RecoursiveQuick(var A: mas; l, r: Integer);

var

m: Integer;

begin

if l < r then

begin

m: = Partition(A, l, r, A[(l + r) div 2]);

RecoursiveQuick(A, l, m);

RecoursiveQuick(A, m + 1, r);

end;

end;

1.4 Сортировка методом Уильямса-Флойда

Метод сортировки массива, предложенный и развитый Вильямсом и Флойдом, носит название алгоритма " пирамиды". Он основан на специальном представлении массива в форме бинарного дерева, обладающего особыми свойствами и называемого " пирамидой". Алгоритм не требует дополнительной памяти. Высокая эффективность алгоритма и гарантированная надежность для самого " худшего" случая часто оказываются решающими факторами, заставляющими отдавать предпочтение этому способу сортировки.

Процесс сортировки состоит из двух этапов. На первом этапе массив преобразуется к виду " пирамиды". На втором этапе осуществляется сортировка " пирамиды".

Под структурой бинарного дерева понимается множество элементов, обладающих иерархией следующего вида:

X[1]

X[2] X[3]

X[4] X[5] X[6 ] X[7]

X[8] X[9]................................

Структура дерева имеет логический характер - в памяти компьютера все элементы массива всеравно расположены последовательно. Каждый элемент в структуре бинарного дерева имеет два элемента-потомка X[2i] и X[2i+1], где i - индекс данного элемента. Элементы массива, являющегося " пирамидой", обладают дополнительными свойствами:

1. Любой элемент пирамиды X[i] не меньше, чем его элементы-потомки X[2i] и X[2i+1] (соответственно первый элемент обладает максимальным значением):

X[i] > = X[2i],

X[i] > = X[2i+1]

2. Любая подпоследовательность элементов вида X[n\2+1], X[n\2+2],... X[n] также является пирамидой, обладающей свойствами 1 и 2. После преобразования массива к форме пирамиды сортировка осуществляется следующим образом.

В массиве-пирамиде первый элемент не меньше остальных. Обменяем его с последним элементом и " укоротим" массив на 1 элемент с " хвост а". Наибольший элемент массива окажется последним. " Укороченная" последовательность элементов может уже не быть пирамидой. Поэтому рассмотрим элемент X[1] и его потомки - X[2] и X[3]. Если элемент не меньше потомков, то последовательность является пирамидой. В противном случае меняем местами элемент X[1] и наибольший из потомков: max(X[2], X[3]). Для элемента-потомка, который обменялся значением, повторяется процесс сравнения и обмена с потомками до тех пор, пока последовательность не станет пирамидой. После циклического повторения описанного этапа сортировки пирамида станет отсортированным массивом. Реализация этого алгоритма в программе 5.

Программа 5. Процедура PiramidaSort

Procedure PiramidaSort(var A: mas);

Var t, k, i, Y: Integer;

Begin

For i: = 2 to N do { создание структуры бинарного дерева-" пирамиды" }

begin

t: = i;

while t < > 1 do

begin k: = t div 2;

If A[k] > = A[t] then t: = 1

else

begin

Y: =A[k]; A[k]: =A[t]; A[t]: =Y;

t: = k;

end

end

end;

For i: = N-1 downto 1 do { сортировка массива-" пирамиды" }

begin

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

t: = 1;

While t < > 0 do

begin

k: = t+t;

If k > i then t: = 0

else

begin

If k < i then If A[k+1] > A[k] then k: = k+1;

If A[t] > = A[k] then t: = 0

else

begin

Y: =A[k]; A[k]: =A[t]; A[t]: =Y;

t: = k

end;

end;

end;

end;

End;