3-й шаг: 3-й и 4-й поменялись местами

I=4

4-й шаг: 4-й и 6-й поменялись местами

I=5

5-й шаг: 5-й и 6-й поменялись местами

Всего N-1=5 шагов. Часть из них результативна (2,3,4,5), а первый шаг никаких перестановок не производит. Отметим, однако, что даже при нерезультативных ходах все циклы работают до конца и за время сортировки внутренний цикл выполнится N(N-1)/2 раз.

13.3 Прямой обмен (метод пузырька, всплытие)

Суть его заключается в том, что в отличие от первых двух методов, где просмотр массива шел по увеличению индекса 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

end;

end.

Работу программы иллюстрирует пример с тем же исходным массивом, что и ранее:

Все остальные обработки при I = 4, 5, 6 идут впустую, т.к. массив уже упорядочен. В других ситуациях может случиться так, что сортировка закончится только на последнем цикле.

13.4 Сравнительная характеристика методов

Все три метода простой сортировки далеки от идеала, однако в некоторых ситуациях их эффективность может оказаться различной. В связи с этим можно выделить следующие случаи:

1. Массив уже отсортирован (но мы не знаем об этом).

Здесь самым быстрым и эффективным следует считать метод прямого включения, т.к. никаких передвижек не произойдет (за счет цикла WHILE, который формально просто не будет работать), а останется только проход по внешнему циклу.

2. Исходный массив упорядочен по убыванию.

Здесь самым лучшим методом является прямой выбор, т.к. вся работа будет проделана за половину ходов (проход до середины):

ПРИМЕР:

3. Массив дан случайным образом.

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

13.5 Улучшенный метод сортировки. QUICK - сортировка

Все рассмотренные выше методы сортировки допускают определенное улучшение. Однако наибольший эффект достигается при модификации наиболее быстрого из всех известных методов - метода прямого обмена. Эта модификация получила название QUICK - сортировка.

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

Эта идея приводит к тому, что нужно построить процедуру, которая допускает обращение самой к себе, т.е. рекурсивную процедуру, имеющую входными параметрами номера элеметов:

1-ый - левый элемент: L,

2-ой - правый элемент: R.

На начало процедуры эти параметры должны получить значения:

L = 1; R = N.

В процедуре используется цикл REPEAT по сближению левой и правой границ.

procedure QUICKSORT (L, R: integer; var M: MAS);

var I,J,W,X: integer;

begin

¦ {Установка границ, от которых идет движение к середине}

¦ 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);

¦

end;

ПОЯСНЕНИE. Рассмотрим работу этой процедуры на примере сортировки следующего массива:

Страницы: 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