Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Метод пузырька
|
|
Пары стоящих рядом элементов просматриваются в направлении снизу вверх и сравниваются. Если верхний элемент оказывается меньше нижнего по рисунку, то они меняются местами. Продолжая этот процесс циклически, мы в конце концов придем к отсортированному файлу. Файл расположен вертикально снизу вверх, чтобы эффект всплывающего пузырька выглядел более наглядно. Элементы с большим значением ключа " всплывают" наверх, после последовательных сравниваний с соседними элементами.
Алгоритм имеет следующий вид.
Время работы алгоритма t примерно оценивается формулой:
t=a*N + b*N, где a, b - неизвестные константы, зависящие от программной реализации алгоритма.
< р4> 2.Модификация метода пузырька
{челночная сортировка является улучшенной версией сортировки пузырьковым методом} procedure Shaker(var item: DataArray; count: integer); var j, k, l, r: integer; x: DataItem; begin l: = 2; r: = count; k: = count; repeat for j: = r downto l do if item[j-1] then begin { обмен } x: = item[j-1]; item[j-1]: = item[j]; item[j]: = x; k: = j; end; l: = k+1; for j: = l to r do if item[j-1]> item[j] then begin { обмен } x: = item[j-1]; item[j-1]: = item[j]; item[j]: = x; k: = j; end; r: = k-1; until l> r end;Модификация метода пузырька состоит в том, что файл можно просматривать как с начала до конца, так и с конца до начала попеременно. Это несколько сокращает число перемещений элементов. Схема перемещений элементов будет в этом случае иметь следующий вид.
Проход 1 осуществлялся с начала в конец, проход 2 - с конца в начало, проход 3 снова с начала в конец и т.д.. Как видно из таблицы, этот алгоритм потребовал на 2 прохода меньше, чем исходный.
Время работы алгоритма t примерно оценивается формулой:
t=a*N + b*N, где a, b - неизвестные константы, зависящие от программной реализации алгоритма.
|
|