Сортировка пузурьковым методом.
Наиболее известной (и наиболее "бесславной") является сорти- ровка пузырьковым методом. Ее популярность объясняется запоминаю- щимся названием и простотой алгоритма. Однако, эта сортировка яв- ляется одной из самых худших среди всех когда-либо придуманных сортировок.
Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название про- исходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень. Ни- же показана самая простая форма программы сортировки методом пу- зырька:
{ сортировка пузырьковым методом} 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езультат на экран дисплея }
typeDataItem = 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 down
to 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; { конец челночной сортировки }
ее нельзя рекомендовать для использования, поскольку время выпол- нения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на нез- начительную величину.
