Метод "Пузырька"
При использовании этого способа требуется самое большее
(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; { конец челночной сортировки }
ее нельзя рекомендовать для использования, поскольку время выполнения
по-прежнему зависит квадратично от числа элементов. Число сравнений не
изменяется, а число обменов уменьшается лишь на незначительную величину.
