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

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

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

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

Таблица 1.

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

44	12	12	12	12	12	12	12
66	44	13	13	13	13	13	13
23	66	44	23	23	23	23	23
45	23	66	44	44	44	44	44
12	45	23	66	66	45	45	45
67	12	45	45	45	66	66	66
13	67	67	67	67	67	67	67
88	88	88	88	88	88	88	88

Программа 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.

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

44	12	12	12	12	12	12	12
66	44	13	13	13	13	13	13
23	66	44	23	23	23	23	23
45	23	66	44	44	44	44	44
12	45	23	66	66	45	45	45
67	12	45	45	45	66	66	66
13	67	67	67	67	67	67	67
88	88	88	88	88	88	88	88

Программа 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;