Обменная сортировка.
Название этой группы методов произошло от основного типа операций, используемого в алгоритмах - обмен двух элементов в файле своими значениями. Эта операция используется и в других группах, поэтому классификацию нельзя признать вполне строгой, но данное разделение, тем не менее, является традиционным. Файл, подлежащий сортировке, в общем случае состоит из элементов-записей, включающих информационную часть и ключи, по которым производится упорядочение по возрастанию. Поскольку информационная часть почти не влияет на процесс сортировки, будем предполагать, что файлы, используемые в примерах, состоит только из элементов-ключей, а информационная часть записи отсутствует.
{сортировка обменом}
for i:=1 to n-1 do
for j:=1 to n-1 do
if a[j]>a[j+1] then
begin
x:=a[j];
a[j+1]:=a[j];
a[j]:=x;
end;
1. Метод пузырька
{сортировка пузырьковым методом}
procedure Bubble(var item: DataArray; count:integer);
var
i,j: integer;
x: DataItem;
begin
for i := 2 to count do
begin
for j := count downto i do
if item[j-1]>item[j] then
begin
x := item[j-1];
item[j-1] := item[j];
item[j] := x;
end;
end;
end;
Пары стоящих рядом элементов просматриваются в направлении снизу вверх и сравниваются. Если верхний элемент оказывается меньше нижнего по рисунку, то они меняются местами. Продолжая этот процесс циклически, мы в конце концов придем к отсортированному файлу. Файл расположен вертикально снизу вверх, чтобы эффект всплывающего пузырька выглядел более наглядно. Элементы с большим значением ключа "всплывают" наверх, после последовательных сравниваний с соседними элементами. Алгоритм имеет следующий вид.
Время работы алгоритма t примерно оценивается формулой: t=a*N + b*N, где a,b - неизвестные константы, зависящие от программной реализации алгоритма.
<р4>2.Модификация метода пузырька
{челночная сортировка является улучшенной версией сортировки
пузырьковым методом}
procedure Shaker(var item: DataArray; count:integer);
var
j, k, l, r: integer;
x: DataItem;
begin
l := 2; r := count; k := count;
repeat
for j := r downto l do
if item[j-1] then
begin { обмен }
x := item[j-1];
item[j-1] := item[j];
item[j] := x;
k := j;
end;
l := k+1;
for j := l to r do
if item[j-1]>item[j] then
begin { обмен }
x := item[j-1];
item[j-1] := item[j];
item[j] := x;
k := j;
end;
r := k-1;
until l>r
end;
Модификация метода пузырька состоит в том, что файл можно просматривать как с начала до конца, так и с конца до начала попеременно. Это несколько сокращает число перемещений элементов. Схема перемещений элементов будет в этом случае иметь следующий вид.
Проход 1 осуществлялся с начала в конец, проход 2 - с конца в начало, проход 3 снова с начала в конец и т.д. . Как видно из таблицы, этот алгоритм потребовал на 2 прохода меньше, чем исходный. Время работы алгоритма t примерно оценивается формулой: t=a*N + b*N, где a,b - неизвестные константы, зависящие от программной реализации алгоритма.