Занятие 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

Dec(j);

if i<=j

then

begin

y := Massiv[i];

Massiv[i] := Massiv[j];

Massiv[j] := y;

Inc(i);

Dec(j);

end;

until i>j;

if Left<j

then

QuickSort (Left, j);

if i<Right

then

QuickSort (i, Right);

End;

Задача. Составьте программу, реализующую рассмотренный метод. Дополните ее комментариями.

Занятие 4. Сортировка методом слияний.

Определение. Целочисленный массив с расположенными по неубыванию или по невозрастанию значениями элементов называется упорядоченным.

Использование упорядоченности позволяет создавать эффективные алгоритмы для решения многих интересных задач.

Задача слияния двух входных упорядоченных массивов А и В состоит в формировании упорядоченного выходного массива С, содержащего все элементы из входных массивов.

Рассмотрим алгоритм слияния для упорядоченных по неубыванию массивов. Вначале элемент А[1] сравнивается с элементом В[1] и наименьший из них записывается в массив С. Если наименьшим был А[1], то на следующем шаге сравниваются А[2] и B[1], а если наименьшим был B[1], то будут сравниваться A[1] и B[2] и т.д. Если на очередном шаге окажется, что из одного входного массива все элементы переписаны в С, то переписывается элемент из другого массива.

Рассмотрим пример работы алгоритма слияния.

Пусть в массиве А содержатся 3 элемента: {5, 13, 14}, а в массиве В – 4 элемента: {7, 9, 10, 12}. Внимательно рассмотрите таблицу, в которой по шагам показано изменение переменных i, i1, i2 и действия с массивами.

i	i1	i2	Сравниваются	C[i]
1 2 3 4 5 6 7	1 2 2 2 2 2 3	1 1 2 3 4 5 5	A[1]=5 и B[1]=7 A[2]=13 и B[1]=7 A[2]=13 и B[2]=9 A[2]=13 и B[3]=10 A[2]=13 и B[4]=12 В весь переписан В весь переписан	5 7 9 10 12 13 14

Рассмотрите фрагмент решения задачи на слияние двух массивов А и В, которые содержат соответственно n1 и n2 элементов. Результирующий массив С будет содержать n1+n2 элементов.

. . .

i1 := 1;

i2 := 1;

for i := 1 to n1+n2 do

if i1>n1

then

begin

C[i] := B[i2];

i2 := i2+1;

end

else

if i2>n2

then

begin

C[i] := A[i1];

i1 := i1+1;

end

else

if A[i1]<=B[i2]

then

begin

C[i] := A[i1];

i1 := i1+1;

end

else

begin

C[i] := B[i2];

i2 := i2+1;

end;

. . .

Задача. Составьте программу, реализующую рассмотренный метод. Дополните ее комментариями.