Урок 1. Алгоритм пузырьковой сортировки (bubble, for, var, TListBox, циклы в Delphi) |
Автор megabax | |||||||
03.09.2009 г. | |||||||
Алгоритм пузырьковой сортировки (bubble, for, var, TListBox, циклы в Delphi)Суть этого алгоритма состоит в том, что элемент сортируемого списка как бы "всплывает", подобно пузырьку (кстати, именно поэтому алгоритм получил свое название), и движется он до тех пор, пока не найден свое место. В реализации этот алгоритм очень прост, смотрите сами:
Если вы внимательно посмотрите на программу, то наверняка сразу зададите вопрос, почему первый цикл начинается со второго элемента? Что бы ответить на него, посмотрим вложенный цикл. Он начинается с конца сортируемого списка и идет в обратном направлении до текущего элемента родительского цикла. Теперь обратим внимание на содержимое вложенного цикла:
Как видим, мы совершаем операции с элементом под номером j-1. На первом проходе это и будет элемент под номером 1 (потому что 2-1=1). Как же работает алгоритм пузырьковой сортировки? Верхний цикл перемещает указать в прямом направлении, за указателем элементы оказываются отсортированными. А непосредственно сортировкой занимается вложенный цикл. Он то и как раз "проталкивает" элемент до своего места, делая это путем перестановок.
Естественно, перестановка нужна только в том случае, когда предыдущий элемент больше текущего - значит, его нужно "опустить", а текущий наоборот, "поднять". Если мы сортируем по убыванию, тогда, естественно, все наоборот. А теперь мы займемся тестированием алгоритма. Разместим на форме компоненты согласно скриншоту*: Поле списка (TListBox), которое отобразит массив до сортировки, назовем lbIn, который после - lbOut, галочка показать результаты (chbShowResults) нужна нам для того, что бы мы могли отключить вывод списка на экран, когда буем тестировать большие списки с целью выяснить быстродействие алгоритма. Поле для ввода количества элементов массива (TSpinEdit) назовем seCount, метки для вывода времени начала и окончания сортировки lbBegSort и lbEndSort соответственно, кнопочку btnSort. Теперь начнем программировать. Вставим текст процедуры Bubble в раздел implementation. В раздел типов добавим новые типы:
Объявим глобальную переменную Ar:DataArray*; У объекта seCount установим свойство зMinValue 1, а MaxValue 800000. Напишем обработчик формы OnCreate:
и обработчик нажатия кнопочки:
Теперь займемся тестирование алгоритма. Запускаем программу и проверяем, как она работает: Теперь давайте проверим, насколько быстро программа обработает большие массивы: А для 40000 элемент потребуется приблизительно в 4 раза больше времени (у нас вложенный цикл, поэтому количество сравнений пропорционально квадрату количества элементов, а число перестановок мы не можем предугадать). Примерно так и вышло: попробуем еще раз в два раза увеличить количество элементов: На сегодня все, а в следующих уроках я расскажу о том, как можно усовершенствовать этот алгоритм. Скриншоты, помеченные знаком *, являются цитатами и иллюстрациями в соответствии со ст. 1274 ГК РФ программного продукта "Delphi", авторское право на который принадлежит Borland Delphi..
|
|||||||
Последнее обновление ( 04.02.2013 г. ) |
« След. |
---|