|
Страница 5 из 60
Сортировка пузурьковым методом Наиболее известной (и наиболее "бесславной") является сорти-
ровка пузырьковым методом. Ее популярность объясняется запоминаю-
щимся названием и простотой алгоритма. Однако, эта сортировка яв-
ляется одной из самых худших среди всех когда-либо придуманных
сортировок.
Сортировка пузырьковым методом использует метод обменной
сортировки. Она основана на выполнении в цикле операций сравнения
и при необходимости обмена соседних элементов. Ее название про-
исходит из-за подобия процессу движения пузырьков в резервуаре с
водой, когда каждый пузырек находит свой собственный уровень. Ни-
же показана самая простая форма программы сортировки методом пу-
зырька:
{ сортировка пузырьковым методом}
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 c a b;
- первый проход: a d c b;
- второй проход: a b d c;
- третий проход: a b c d.
При анализе всякой сортировки определяется число операций
сравнения и обмена, выполняемых в лучшем, среднем и худших случа-
ях. Для сортировки пузырьковым методом число сравнений остается
неизменным, поскольку два цикла всегда выполняются заданное число
раз вне зависимости от упорядоченности исходного массива. Это оз-
начает, что при сортировке пузырьковым методом всегда выполняется
1/ 2 (n**2-n) операций сравнения, где "n" задает число сортируе-
мых элементов массива. Эта формула выводится на том основании,
что внешний цикл сортировки пузырьковым методом выполняется n-1
раз, а внутренний цикл выполняется n/2 раз. Их перемножение даст
указанную формулу.
Число операций обмена будет нулевым для наилучшего случая,
когда исходный массив уже является отсортированным. Число опера-
ций обмена для среднего случая будет равно 3/4 (n**2-n), а для
наихудшего случая будет равно 3/2 (n**2-n) раз. Вывод этих формул
выходит за пределы этой книги. Можно заметить, что по мере ухуд-
шения упорядоченности исходного массива число неупорядоченных
элементов приближается к числу сравнений (каждый неупорядоченный
элемент требует три операции обмена). Сортировку пузырьковым ме-
тодом называют квадратичным алгоритмом, поскольку время его вы-
полнения пропорционально квадрату числа сортируемых элементов.
Сортировка большого числа элементов пузырьковым методом потребует
очень много времени, т.к. время выполнения сортировки находится в
квадратичной зависимости от числа элементов массива.
Например, если не учитывать время операций обмена, выполняе-
мых для перестановки неупорядоченных элементов, то тогда при вы-
полнении одной операции сравнения в течение 0,001 секунд сорти-
ровка десяти элементов займет 0,05 секунд, сортировка ста
элементов займет пять секунд, а сортировка 1000 элементов займет
500 секунд. Сортировка 100 000 элементов (такой размер имеет не-
большой телефонный справочник) потребовала бы 5000000 секунд или
около 1400 часов (т.е. два месяца непрерывной работы)!
Сортировку пузырьковым методом можно в некоторой степени
улучшить и тем самым немного улучшить ее временные характеристи-
ки. Можно, например, заметить, что сортировка пузырьковым методом
обладает одной особенностью: расположенный не на своем месте в
конце массива элемент (например, элемент "а" в массиве "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; { конец челночной сортировки }
ее нельзя рекомендовать для использования, поскольку время выпол-
нения по-прежнему зависит квадратично от числа элементов. Число
сравнений не изменяется, а число обменов уменьшается лишь на нез-
начительную величину. |