Метод "Пузырька"

При использовании этого способа требуется самое большее (n-1) проходов. В течение первого прохода таблицы сравниваются ключи К1 и К2 первой и второй записей, и, если порядок между ними нарушен, то записи R1 и R2 меняются местами. Затем этот процесс повторяется для записей R2 и R3, R3 и R4 и т.д. Данный метод заставляет двигаться, или "всплывать", записи с малыми ключами. Поспервого прохода запись с наибольшим ключом будет находиться на n - й позиции таблицы. При каждом последующем проходе записи со следующем наибольшим ключом будут располагаться в позициях n-1, n-2, ... , 2 соответственно, в
результате чего будет сформирована отсортированная таблица. После каждого прохода через таблицу может быть сделана проверка, были ли совершены перестановки в течение данного прохода. Если перестановок не было, то это означает, что таблица уже отсортирована и дальнейших проходов не требуется. Кроме того,можно запоминать индекс последней перестановки. Это позволит уменьшить на следующем шаге просматриваемую подтаблицу.
Характеристики сортировки методом "пузырька" в худшем случае составляют n(n-1)/2 сравнений и n(n-1)/2 перестановок (худшим считается случай,когда элементы наиболее удалены от своих конечных позиций).
Среднее число сравнений и перестановок имеет порядок n**2 .

Процедура, реализующая метод "пузырька" на языках Паскаль и Си, приведена ниже.

Type ¦ typedef
Rec=Record ¦ struct{
f1 : char; ¦ char f1;
f2 : integer; ¦ int f2;
f3 : integer ¦ int f3; } rec;
End;
Table = Array[1..100] Of Rec; ¦ rec[100] table;
procedure bubble(var T:Table; ¦ void bubble(table *t,int n);
n:integer); ¦ /* t - таблица */
{ T - таблица; n - ее размер } ¦ /* n - количество записей */
{ сортировка по полю f3} ¦ /* сортировка по полю f3 */
¦ {
var ¦ int i,j,pr;
i:integer; ¦ rec el;
temp:Rec; ¦ /* сортировка по полю f3 */
switch:boolean; ¦ do{
begin ¦ pr=0;
repeat ¦ for( j=0;j<n;j++)
switch:=false; ¦ {
for i:=1 to n-1 do ¦ if(*t[j].f3>*t[j+1].f3)
if T[i].f3>T[i+1].f3 then ¦ {
begin ¦ el=*t[j];
switch:=true; ¦ *t[j]=*t[j+1];
temp:=T[i]; ¦ *t[j+1] = el;
T[i]:=T[i+1]; ¦ pr=1;
T[i+1]:=temp ¦ }
end ¦ }
until not(switch) ¦ }while(pr==1);
end ¦ }

Сортировка пузурьковым методом.

Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень. Ниже показана самая простая форма программы сортировки методом пу зырька:
{ сортировка пузырьковым методом}
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; {конец сортировки пузырьковым методом}

В этом случае данное "item" является массивом элементов "DataItem", который сортируется, а данное "count" содержит число элементов в массиве. Сортировка пузырьковым методом имеет два цикла. Поскольку число элементов массива задается переменной "count", внешний цикл вызывает просмотр массива count - 1 раз. Это обеспечивает нахождение каждого элемента в своей позиций после завершения процедуры. Внутренний цикл предназначен для фактического выполнения операций сравнения и обмена. Эта версия сортировки пузырьковым методом может сортировать символьный массив в порядке возрастания значений элементов. Нап ример, следующая короткая программа сортирует строку, которая считывается с дискового файла "test.dat". Эта же программа может использоваться с другими подпрограммами сортировки, которые при водятся в этой главе.

program SortDriver;

{эта программа будет считывать 80 или меньше символов с
дискового файла "test.dat", отсортирует их и выдаст
pезультат на экран дисплея }

type
DataItem = char;
DataArray = array [1..80] of char;
var
test: DataArray;
t, t2: integer;
testfile: file of char;
{ сортировка пузырьковым методом}
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;
begin
Assign(testfile, 'test.dat');
Reset(testfile);
t := 1;

{ считывание символов,которые будут сортироваться.}

while not Eof(testfile) do begin
read(testfile, test[t]);
t := t+1;
end;
t := t-2; {скорректировать число считанных элементов }

Bubble(test, t); { сортировать массив }

{ выдать отсортированный массив символов }
for t2 := 1 to t do write(test[t2]);
WriteLn;
end.

Сортировку пузырьковым методом можно в некоторой степени улучшить и тем самым немного улучшить ее временные характеристи ки. Можно, например, заметить, что сортировка пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент (например, элемент "а" в массиве "dcab") достигает своего места за один проход, а элемент, расположенный в начале массива (например, элемент "d"), очень медленно достигает своего места. Необязательно все просмотры делать в одном направлении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении. В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место. Ниже показана улучшенная версия сортировки пузырьковым методом, получившая название "челночной сортировки" из-за соот ветствующего характера движений по массиву. Хотя эта сортировка является улучшением пузырьковым методом, ее нельзя рекомендовать для использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.
{ челночная сортировка является улучшенной версией сортировки пузырьковым методом }

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; { конец челночной сортировки }

ее нельзя рекомендовать для использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.