Занятие 3. Сортировка методом простого обмена. Рекурсивная сортировка

Принцип метода:

Слева направо поочередно сравниваются два соседних элемента, и если их взаимное расположение не соответствует заданному условию упорядоченности, то они меняются местами. Далее берутся два следующих соседних элемента и так далее до конца массива.

После одного такого прохода на последней n-ой позиции массива будет стоять максимальный (или минимальный) элемент ("всплыл" первый "пузырек"). Поскольку максимальный (или минимальный) элемент уже стоит на своей последней позиции, то второй проход обменов выполняется до (n-1)-го элемента. И так далее. Всего требуется (n-1) проход.

Задание. В тетради начертите схему работы рассмотренного алгоритма произвольно выбранного массива.

Рассмотрите процедуру, реализующую выше рассмотренный алгоритм:

Procedure Obmen(Var a: Array1);

Var

i,j,f,g:integer;

Begin

for i:=n downto 2 do

for j:=1 to i-1 do

if a[j]>a[j+1]

then

begin

f:=a[j];

a[j]:=a[j+1];

a[j+1]:=f;

end;

End;

Задание. Составьте программу сортировки одномерного массива рассмотренным методом.

Cортировка массива с помощью рекурсии.

Рассмотрим использование рекурсии для построения алгоритма сортировки значений массива.

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

Рассмотрите процедуру, упорядочивающую по возрастанию значения из массива Massiv в диапазоне индексов Left..Right.

Procedure QuickSort (Left, Right: integer; Massiv: Array1);

Var

i, j, x, y: integer;

Begin

i:= Left;

j:= Right;

x:= Massiv[(Left+Right) div 2];{}

repeat

while Massiv[i]<x do

Inc(i);

while Massiv[j]>x do