![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Метод пузырька
Пары стоящих рядом элементов просматриваются в направлении снизу вверх и сравниваются. Если верхний элемент оказывается меньше нижнего по рисунку, то они меняются местами. Продолжая этот процесс циклически, мы в конце концов придем к отсортированному файлу. Файл расположен вертикально снизу вверх, чтобы эффект всплывающего пузырька выглядел более наглядно. Элементы с большим значением ключа " всплывают" наверх, после последовательных сравниваний с соседними элементами. Время работы алгоритма t примерно оценивается формулой: < р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 прохода меньше, чем исходный.
|