Энциклопедия Turbo Pascal. Главы 1-4 - Сортировка пузырьковым методом

ОГЛАВЛЕНИЕ

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

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

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

        { сортировка пузырьковым методом}
       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; { конец челночной сортировки  }

ее нельзя рекомендовать для использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов.  Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину.