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

Наиболее известной (и наиболее "бесславной") является сортировка пузырьковым методом. Ее популярность объясняется запоминающимся названием и простотой алгоритма. Однако, эта сортировка является одной из самых худших среди всех когда-либо придуманных сортировок.

Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень. Ниже показана самая простая форма программы сортировки методом пузырька:

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; 

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

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

program SortDriver;

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.