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

{сортировка обменом}
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 - неизвестные константы, зависящие от программной реализации алгоритма.
3. Быстрая сортировка.

{быстрая сортировка}
procedure QuickSort(var item: DataArray; count:integer);
procedure qs(l, r: integer; var it: DataArray);
var
i, j: integer;
x, y: DataItem;
begin
i:=l; j:=r;
x:=it[(l+r) div 2];
repeat
while it[i]<x do i := i+1;
while x<it[j] do j := j-1;
if y<=j then
begin
y := it[i];
it[i] := it[j];
it[j] := y;
i := i+1; j := j-1;
end;
until i>j;
if l<j then qs(l, j, it);
if l<r then qs(i, r, it)
end;
begin
qs(1, count, item);
end;
type
DataItem = string[80];
DataArray = array [1..80] of DataItem;

{алгоритм быстрой сортировки для символьных строк }
procedure QsString(var item: DataArray; count:integer);
procedure qs(l, r: integer; var it:DataArray);
var
i, l: integer;
x, y: DataItem;
begin
i := l; j := r;
x := it[(l+r) div 2];
repeat
while it[i] < x do i := i+1;
while x < it[j] do j := j-1;
if i<=j then
begin
y := it[i];
it[i] := it[j];
it[j] := y;
i := i+1; j := j-1;
end;
until i>j;
if l<j then qs(l, j, it);
if l<r then qs(i, r, it);
end;
begin
qs(1, count, item);
end;

{быстрая сортировка записей с почтовым адресом}
procedure QsRecord(var item: DataArray; count:integer);
procedure qs(l, r:integer; var it:DataArray);
var
i, j: integer;
x, y: DataItem;
begin
i := l; j := r;
x := it[(l+r) div 2];
repeat
while it[i].name < x.name do i := i+1;
while x.name < it[j].name do j := j-1;
if i<=j then
begin
y := it[i];
it[i] := it[j];
it[j] := y;
i := i+1; j := j-1;
end;
until i>j;
if l<j then qs(l, j, it);
if l<r then qs(i, r, it)
end;
begin
qs(1, count, item);
end;

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

программирование

Сортировка подфайлов, содержащих меньше чем М элементов, выполняется каким-либо простым методом, например простыми вставками. Таким образом, реализация метода зависит от двух параметров: значения М и способа выбора элемента, который предназначен для разделения файла на две части. Блок выбора Х в простейшем случае формулируется как X=K[l], однако это может привести к крайне неэффективному алгоритму. Наиболее простое лучшее решение - выбирать Х как случайный ключ из диапазона K[l] ... K[r] и обменять его с K[l].
4. Обменная поразрядная сортировка

Данный метод использует двоичное представление ключей. Файл сортируется последовательно по битам двоичного представления ключей, начиная со старшего. Ключи, имеющие значение данного бита, равное нулю, ставятся в левую половину файла, а ключи со значением бита 1 - в правую. Ниже приведена схема алгоритма поразрядной сортировки. Функция b(ключ) возвращает значение с номером b аргумента, m - максимальное количество значащих битов в ключах.

программирование
5. Параллельная сортировка Бэтчера

Для получения алгоритма обменной сортировки, время работы которого меньше, чем N, необходимо выбирать для сравнения и обмена ключи, расположенные возможно дальше друг от друга. Эта идея уже была реализована в алгоритме сортировки Шелла вставок с убывающим шагом, однако в данном алгоритме сравнения выполняются по-другому. Рассмотрим схему алгоритма. Здесь t= <logN> - наименьшее целое,
равное или превышающее logN ( N>=2). Переменная d имеет смысл шага
сортировки, то есть сравниваются ключи K[i] и K[i+d]. Через <-> обозначена операция обмена значений двух переменных.

программирование

На схеме алгоритма через & обозначена операция поразрядного И, то есть выполнение условия i&p = r означает, что в цикле по i нужно выбирать только такие значения i, которые в одном разряде, изменяющемся в цикле по p (операция p=p/2 имеет смысл сдвига начального значения 1 в разряде (t-1), имеют сначала значение 0 (поскольку r=0), а затем 1 (поскольку r=p).