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