Полный обучающий курс (стр. 35 )

1) сортировка вставкой (включением);

2) сортировка выбором (выделением);

3) сортировка обменом (так называемая "пузырьковая" сортировка).

Улучшенные методы сортировки основываются на тех же принципах, что и прямые, но используют некоторые оригинальные идеи для ускорения процесса

Рассмотрим сортировку методом вставки.

Принцип метода заключается в следующем:

Массив разделяется на две части: отсортированную и не отсортированную. элементы из не отсортированной части поочередно выбираются и вставляются в отсортированную часть так, чтобы не нарушить в ней упорядоченность элементов. В начале работы алгоритма в качестве отсортированной части массива принимают только первый элемент, а в качестве не отсортированной – все остальные элементы.

Таким образом, алгоритм будет состоять из (n-1)-го прохода (n – размерность массива), каждый из которых будет включать четыре действия:

• взятие очередного i-го не отсортированного элемента и сохранение его в дополнительной переменной;

• поиск позиции j в отсортированной части массива, в которой присутствие взятого элемента не нарушит упорядоченности элементов;

• сдвиг элементов массива от i-го до j-1-го вправо, чтобы освободить найденную позицию вставки;

• вставка взятого элемента в найденную i-ю позицию.

Для реализации данного метода можно предложить несколько алгоритмов, которые будут отличаться способом поиска позиции вставки.

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

Procedure Vstavka(Var a : Array1);

Var

i, j, e,g:integer;

Begin

for i:=2 to c do

begin

e:=A[i];

j:=1;

while (e>a[j]) do

Inc(j);

for g:=i-1 downto j do

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

a[j]:=e;

end;

End;

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

Сортировка выбором

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

Находим (выбираем) в массиве элемент с минимальным значением на интервале от 1-го элемента до n-го (последнего) элемента и меняем его местами с первым элементом. На втором шаге находим элемент с минимальным значением на интервале от 2-го до n-го элемента и меняем его местами со вторым элементом. И так далее для всех элементов до n-1-го.

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

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

Procedure Vibor(Var a: Array1);

Var

i, j, Min, MinI : integer;

Begin

for i:=1 to c do

begin

Min:=a[i];

MinI:=i;

for j:=i+1 to c do

if a[j]<Min

then

begin

Min:=a[j];

MinI:=j;

end;

a[MinI]:=a[i];

a[i]:=Min;

end;

End;

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

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

. . .

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

Для любопытных. Рекурсивная сортировка слиянием

Задача. Напишите программу, содержащую алгоритм слияния в процедуре Sort(A, B, b1, e1, e2). Алгоритм должен копировать со слиянием два упорядоченные куска из массива А с номерами от b1 до e1 и от e1+1 до e2 соответственно в массив В с номерами элементов от b1 до e2.

Предположив, что Вы правильно выполнили предыдущую задачу, алгоритм сортировки можно определить очень просто:

1) если длина сортируемого массива 1, то ничего не делается;

2) в противном случае массив делится на две одинаковые (или почти одинаковые) части, к каждой части применяется алгоритм сортировки, после чего эти упорядоченные части сливаются в один упорядоченный кусок.

Рассмотрите процедуру сортировки слиянием. На вход процедуры сортировки поступает неупорядоченный кусок массива А с номерами элементов от b до e, на выходе – тот же кусок, но упорядоченный. Массив С – вспомогательный.

Procedure Sort2(Var A, C : Array1; b, e : integer);

Var

i, d : integer;

Begin

if b<e

then

begin

d := (b+e) div 2;

Sort2(A, C, b, d);

Sort2(A, C, d+1, e);

Sort(A, C, b, d, e);

for i := b to e do

A[i] := C[i]

end;

End;

Занятие 5-6. Самостоятельное решение задач.

Задание. Выберите с учителем задачи для решения из предложенного ниже перечня.

1. В массиве X(N) каждый элемент равен 0, 1 или 2. Переставить элементы массива так, чтобы сначала располагались все единицы, затем все двойки и, наконец, все нули (дополнительного массива не заводить).

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

3. Отсортировать массив по возрастанию, используя процедуру Swap, которая меняет местами 2 элемента.

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

5. Из двух упорядоченных одномерных массивов (длины K и N) сформируйте одномерный массив размером K+N, упорядоченный так же, как исходные массивы.