Урок 2. Оптимизация алгоритма пузырьковой сортировки (bubble, for, var, TListBox, циклы в Delphi)

Автор megabax

19.11.2009 г.

Циклы

Оптимизация алгоритма пузырьковой сортировки (bubble, for, var, TListBox, циклы в Delphi)

Для этого урока понадобятся материалы прошлого урока.

Суть данного алгоритма нам должна быть понятна с предыдущего урока. Но сейчас перед нами стоит цель провести оптимизацию кода таким образом, чтобы получить полную отдачу от данного метода сортировки.

Алгоритм пузырьковой сортировки очень медленный, за исключением случаев, когда массив или часть массива уже отсортированы - в данном случае, мы ограничим число проходов, сведя их к минимуму, либо достаточно будет одного прохода, если массив уже отсортирован. Рассмотрим, как это будет вызлядеть, на примере. Возьмем массив чисел, частично упорядочив его:

7 3 1 2 3

Теперь рассмотрим как будет проходить сортировка. Сравниваем все элементы массива между собой (сравниваемые элементы выделены жирным шрифтом), естественно смещая более тяжелые вправо, а более легкие влево, либо оставляя их на местах, если они равны (тем самым уменьшая число операций присваивания):

Первый проход по внешнему цыклу:

7 3 1 2 3                      >> обмен
3 7 1 2 3                      >> обмен
3 1 7 2 3                      >> обмен
3 1 2 7 3                      >> обмен

Второй проход по внешнему цыклу:

3 1 2 3 7                      >> обмен
1 3 2 3 7                      >> обмен
1 2 3 3 7                      >> пропускаем обмен

Третий проход по внешнему цыклу:

1 2 3 3 7 >> пропускаем обмен
1 2 3 3 7 >> пропускаем обмен

Здесь можно увидеть, что с каждым последующих шагом внешнего цикла, число сравниваемых элементов уменьшается на единицу. Это связанно с тем, что нет необходимости сортировать ту часть элементов, которую мы уже отсортировали. На последнем шагу так-же видно, что мы прерываем цикл. Это связанно с тем, что не было проведено ни одного обмена, а следовательно массив является отсортированным и нет смысла продолжать дальнейшую обработку массива. Вот так выглядит модель правильной пузырьковой сортировки. Теперь попробуем переделать нашу процедуру (см. предыдущий урок) сортировки таким образом, чтобы она была наиболее приближена к нашей модели:

procedure Bubble2(var item: DataArray; count:integer);
var
i,j: integer;
x: DataItem;
flag: Boolean;
begin
flag := False;
for i := 2 to count do
    begin
      flag := True;   // Присваиваем True, для прерывания цикла если не будет обмена элементами.
      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;
          flag := False;   // Говорим что обмен был, и прерывать цикла нельзя.
        end;
      if flag then Break;   // Прерываем внешний цикл, если обмена не было
    end;
end;

Посмотрим, что у нас получилось. Была создана еще одна процедура - Bubble2, которая отличается от Bubble лишь тем, что была добавлена переменная flag логического типа, которая нам будет сообщать, можно ли прервать внешний цыкл в связи с завершением сортировки.

Теперь нам потребуется добавить еще одну кнопку "Сотировать 2" (btnSort2), и на ее обработку событие нажатия клавиши полностью скопируем обработку события нажатия клавиши с кнопки "Сотировать" (btnSort), лишь заменив вызов процедуры Bubble на Bubble2.

Теперь начнем наши тесты:

На рисунке слева мы видим время сортировки посредством выполнения процедуры "Bubble", ну а на втором посредством процедуры "Bubble2". Что мы видим, время выполнения абсолютно идеентично. Это что-же,получается, оптимизации никакой не произошло? Нет, оптимизация проведена, как я писал выше - "Алгоритм пузырьковой сортировки очень медленный, за исключением случаев, когда массив или часть массива уже отсортированы". Давайте попробуем немного упорядочить последовательность символов массива. Проведем следующие изменения в обработчиках нажатия кнопок :

var
   ...
   cSort: LongInt;
begin
  ...
cSort := round(cn/2);
  for i := 1 to cn do
begin
    if cSort > i then
      ar[i] := i
    else
      ar[i] := random(1000);
    ...
end;
   ...

И так, что же у нас получилось, теперь половина символов у нас будет отсортированы, а вторая половина так-же заполнена случайным образом. Проведем тест и посмотрим что у нас получится:

Как видно на картинках, оптимизация по времени есть, но она невелика. А есть ли вообще смысл использовать ее??? Давайте проведем еще один опыт. Попробуем прогнать через алгоритм уже отсортированный массив. Для этого проведем очередное изменение кода обработчиков события нажатия кнопок:

   ...
begin
  ...
  for i := 1 to cn do
  begin
    ar[i] := i
    //ar[i] := random(1000);
    ...
end;
   ...

Таким образом мы получим уже отсортированный массив, который не нуждается в сортировке. Давайте посмотрим каков будет результат:

Что-же мы видим? Первый вариант по прежнему тратит время на сортировку уже отсортированного массива, в то время как второй вариант затратил на выполнение минимум времени.

Таким образом мы увидели, что оптимизация данного алгоритма позволила нам сократить время лишь на обработке частично отсортированных массивах, ну а на сортировке уже отсортированных массивов мы получили оптимальный вариант, так-как для проверки массива нам хватило лишь одного прохода по массиву, чтобы определить, что массив уже отсортирован и прекратить сортировку.

Скриншоты, помеченные знаком *, являются цитатами и иллюстрациями программного продукта "Delphi", авторское право на который принадлежит Borland Delphi..

Последнее обновление ( 09.02.2013 г. )