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

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

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

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;

Если вы внимательно посмотрите на программу, то наверняка сразу зададите вопрос, почему первый цикл начинается со второго элемента?  Что бы ответить на него, посмотрим вложенный цикл. Он начинается с конца сортируемого списка и идет в обратном направлении до текущего элемента родительского цикла. Теперь обратим внимание на содержимое вложенного цикла:

if item[j-1]>item[j] then
   begin
          x := item[j-1];
          item[j-1] := item[j];
          item[j] := x;
   end;

Как видим, мы совершаем операции с элементом под номером j-1. На первом проходе это и будет элемент под номером 1 (потому что 2-1=1).

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

x := item[j-1];
item[j-1] := item[j];
item[j] := x;

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

А теперь мы займемся тестированием алгоритма. Разместим на форме компоненты согласно скриншоту*:

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

Поле списка (TListBox), которое отобразит массив до сортировки, назовем lbIn, который после - lbOut, галочка показать результаты (chbShowResults) нужна нам для того, что бы мы могли отключить вывод списка на экран, когда буем тестировать большие списки с целью выяснить быстродействие алгоритма. Поле для ввода количества элементов массива (TSpinEdit) назовем seCount, метки для вывода времени начала и окончания сортировки lbBegSort и lbEndSort соответственно,  кнопочку btnSort.

Теперь начнем программировать. Вставим текст процедуры Bubble в раздел implementation. В раздел типов добавим новые типы:

DataItem = integer;
DataArray = array [1..800000] of integer;

Объявим глобальную переменную Ar:DataArray*;

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

У объекта seCount установим свойство зMinValue 1, а MaxValue 800000.

Напишем обработчик формы OnCreate:

procedure TfrmBubble.FormCreate(Sender: TObject);
begin
  randomize;
end;

и обработчик нажатия кнопочки:

procedure TfrmBubble.btnSortClick(Sender: TObject);
var i,cn:LongInt;
begin
   cn:=seCount.Value;
   lbIn.Clear;
   lbOut.Clear;
   for i:=1 to cn do
   begin
     ar[i]:=random(1000);
     if chbShowResults.Checked then lbIn.Items.Add(IntToStr(ar[i]));
   end;
   lbBegSort.Caption:=TimeToStr(Time);
   Bubble(ar, cn);
   lbEndSort.Caption:=TimeToStr(Time);
   if chbShowResults.Checked then for i:=1 to cn do lbOut.Items.Add(IntToStr(ar[i]));
end;

Теперь займемся тестирование алгоритма. Запускаем программу и проверяем, как она работает:

Алгоритм пузырьковой сортировки (bubble, for, var, TListBox)

Теперь давайте проверим, насколько быстро программа обработает большие массивы:

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

А для 40000 элемент потребуется приблизительно в 4 раза больше времени (у нас вложенный цикл, поэтому количество сравнений пропорционально квадрату количества элементов, а число перестановок мы не можем предугадать). 

Примерно так и вышло:

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

попробуем еще раз в два раза увеличить количество элементов:

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

На сегодня все, а в следующих уроках я расскажу о том, как можно усовершенствовать этот алгоритм.


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


 

 

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