Категории раздела
J2me|java [29]
Basic [6]
Delphix [21]
C+|C++|C# [3]
Pascal [10]
Другие [0]
языки которые не войшли в верхние разделы
Главная » Статьи » Программирования » Pascal

Сортировка методом пузырька, плюсы и минусы

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

       
 

              Наиболее известной (и наиболее "бесславной") является сорти-

         ровка пузырьковым методом. Ее популярность объясняется запоминаю-

         щимся названием и простотой алгоритма. Однако, эта сортировка яв-

         ляется  одной  из  самых худших среди всех когда-либо придуманных

         сортировок.

              Сортировка пузырьковым  методом  использует  метод  обменной

         сортировки. Она основана на выполнении в цикле операций сравнения

         и  при необходимости обмена соседних элементов.  Ее название про-

         исходит из-за подобия процессу движения пузырьков в резервуаре  с

         водой, когда каждый пузырек находит свой собственный уровень. Ни-

         же показана самая простая форма программы сортировки методом  пу-

         зырька:

               { сортировка пузырьковым методом} 

 

                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"), очень медленно достигает

         своего места.  Необязательно все просмотры делать в одном направ-

         лении.  Вместо этого всякий последующий просмотр можно  делать  в

         противоположном  направлении.  В  этом случае сильно удаленные от

         своего места элементы будут быстро перемещаться в соответствующее

         место. Ниже показана улучшенная версия сортировки пузырьковым ме-

         тодом, получившая название  "челночной  сортировки"  из-за  соот-

         ветствующего характера движений по массиву.

              Хотя эта сортировка является улучшением пузырьковым методом,

         ее нельзя рекомендовать для использования, поскольку время выпол-

         нения по-прежнему зависит квадратично от числа  элементов.  Число

         сравнений не изменяется, а число обменов уменьшается лишь на нез-

         начительную величину.

Категория: Pascal | Добавил: graimp (21.12.2011)
Просмотров: 1439 | Рейтинг: 0.0/0
Всего комментариев: 0
Имя *:
Email *:
Код *:
Наш опрос
Оцените мой сайт
Всего ответов: 25
Статистика

Онлайн всего: 1
Гостей: 1
Пользователей: 0