Программирование - это просто
Advertisement
Главная arrow Уроки программирования arrow Алгоритмы arrow Урок 2. Оптимизация алгоритма пузырьковой сортировки (bubble, for, var, TListBox, циклы в Delphi)
28.02.2024 г.
Главное меню
Главная
Интернет магазин
Программные продукты
Биржевые роботы
Искусственный интеллект
Математика и информатика
1С:Предприятие
Уроки C#
Уроки Delphi
Уроки программирования
Web-программирование
Дизайн и графика
Компьютер для блондинок
Исходники
Статьи
Платный раздел
Рассказы про компьютеры
Хитрости и секреты
Системный подход
Размышления
Наука для чайников
Друзья сайта
Excel-это не сложно
Все о финансах
.
Урок 2. Оптимизация алгоритма пузырьковой сортировки (bubble, for, var, TListBox, циклы в Delphi) Печать E-mail
Автор 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, for, var, TListBox, циклы в Delphi bubble, for, var, TListBox, циклы в Delphi

На рисунке слева мы видим время сортировки посредством выполнения процедуры "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;
   ...

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

bubble, for, var, TListBox, циклы в Delphi bubble, for, var, TListBox, циклы в Delphi

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

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

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

bubble, for, var, TListBox, циклы в Delphi bubble, for, var, TListBox, циклы в Delphi

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

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

 


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


Последнее обновление ( 09.02.2013 г. )
 
« След.   Пред. »
 
© 2024 Программирование - это просто
Joomla! - свободное программное обеспечение, распространяемое по лицензии GNU/GPL.
Русская локализация © 2005-2008 Joom.Ru - Русский Дом Joomla!
Design by Mamboteam.com | Powered by Mambobanner.de
Я принимаю Яндекс.Деньги