3-й шаг: 3-й и 4-й поменялись местами
I=4
-3
1
2
3
6
4
4-й шаг: 4-й и 6-й поменялись местами
I=5
5-й шаг: 5-й и 6-й поменялись местами
Всего N-1=5 шагов. Часть из них результативна (2,3,4,5), а первый шаг никаких перестановок не производит. Отметим, однако, что даже при нерезультативных ходах все циклы работают до конца и за время сортировки внутренний цикл выполнится N(N-1)/2 раз.
Суть его заключается в том, что в отличие от первых двух методов, где просмотр массива шел по увеличению индекса I, т.е. от начала массива к концу, здесь производится проход от конца массива к началу до I-го элемента, и каждый раз, если А[J-1] > А[J], они меняются местами.
В этом методе также есть два вложенных цикла: внешний цикл поидет от 2 до N, а внутренний по J - от N до I:
for I:= 2 to N do
for J:= N downto I do
{ Обмен местами (всплытие) более легкого элемента }
end;
end.
ОБЩИЙ ВИД ПРОГРАММЫ:
procedure BUBLESORT (var MM: MAS);
var I,J,X: integer;
begin
¦ for I:=2 to N do
¦ for J:= N downto I do
¦ if MM[J-1] > MM[J] then
¦ begin
¦ ¦ X:= MM[J-1];
¦ ¦ MM[J-1]:= MM[J];
¦ ¦ MM[J]:= X
Работу программы иллюстрирует пример с тем же исходным массивом, что и ранее:
I=2
I=3
J=6
J=5
J=4
J=3
J=2
Все остальные обработки при I = 4, 5, 6 идут впустую, т.к. массив уже упорядочен. В других ситуациях может случиться так, что сортировка закончится только на последнем цикле.
Все три метода простой сортировки далеки от идеала, однако в некоторых ситуациях их эффективность может оказаться различной. В связи с этим можно выделить следующие случаи:
1. Массив уже отсортирован (но мы не знаем об этом).
Здесь самым быстрым и эффективным следует считать метод прямого включения, т.к. никаких передвижек не произойдет (за счет цикла WHILE, который формально просто не будет работать), а останется только проход по внешнему циклу.
2. Исходный массив упорядочен по убыванию.
Здесь самым лучшим методом является прямой выбор, т.к. вся работа будет проделана за половину ходов (проход до середины):
ПРИМЕР:
1 шаг:
8
0
2 шаг:
Результат:
3. Массив дан случайным образом.
Здесь два метода - "включение" и "выбор" - равнозначны. Метод "пузырька" наиболее медленный из всех. Здесь при каждом проходе чаще всего идет обмен соседних элементов. Даже в случае уже отсортированного массива, хотя сами перестановки и не совершаются, внутренний цикл сравнивает все соcедние элементы.
Все рассмотренные выше методы сортировки допускают определенное улучшение. Однако наибольший эффект достигается при модификации наиболее быстрого из всех известных методов - метода прямого обмена. Эта модификация получила название QUICK - сортировка.
Суть метода - в середине массива выбирается некоторый граничный элемент, разбивающий весь массив на левую и правую части. Производится одновременное движение слева и справа; если слева находится элемент, больший граничного, то они меняются местами и поиск таких элементов продолжается дальше до границы. Подобная операция повторяется отдельно с левой и правой частями и т.д.
Эта идея приводит к тому, что нужно построить процедуру, которая допускает обращение самой к себе, т.е. рекурсивную процедуру, имеющую входными параметрами номера элеметов:
1-ый - левый элемент: L,
2-ой - правый элемент: R.
На начало процедуры эти параметры должны получить значения:
L = 1; R = N.
В процедуре используется цикл REPEAT по сближению левой и правой границ.
procedure QUICKSORT (L, R: integer; var M: MAS);
var I,J,W,X: integer;
¦ {Установка границ, от которых идет движение к середине}
¦ I:= L; J:= R;
¦ {Выбор граничного элемента}
X:= M[(L+R) div 2];
¦ repeat
¦ ¦ { Поиск слева элемента, большего X }
¦ ¦ while X > M[I] do I:= I+1;
¦ ¦ { Поиск справа элемента, меньшего X }
¦ ¦ while X < M[J] do J:= J-1;
¦ ¦ if I <= J then
¦ ¦ begin
¦ ¦ ¦ W:= M[I]; {Обмен местами
¦ ¦ ¦ M[I]:= M[J]; I-го и J-го
¦ ¦ ¦ M[J]:= W; элементов,
¦ ¦ ¦ I:=I+1; дальнейшее продвижение
¦ ¦ ¦ J:=J-1; вперед (назад)}
¦ ¦ end;
¦ ¦ {Выход из цикла, если левый край перевалил за правый}
¦ until I > J;
¦ { Повтор обмена для левой части }
¦ if L < J then QUICKSORT (L,J,M);
¦ { Повтор обмена для правой части }
¦ if R > i then QUICKSORT (I,R,M);
¦
ПОЯСНЕНИE. Рассмотрим работу этой процедуры на примере сортировки следующего массива:
7
5
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39