Занятие 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]
			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 В весь переписан В весь переписан

Рассмотрите фрагмент решения задачи на слияние двух массивов А и В, которые содержат соответственно 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, упорядоченный так же, как исходные массивы.

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

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

8. Дан упорядоченный целочисленный массив. Сформировать второй массив всех таких различных значений, которые в первом массиве встречаются по два и более раза.

9. Дан упорядоченный целочисленный массив. Сформировать второй массив всех таких различных чисел, которые ни разу в первом массиве не встречаются и имеют величину больше минимального и меньше максимального из чисел первого массива.

10. Дана вещественная матрица размером 7x4. Переставляя ее строки и столбцы, добиться того, чтобы наибольший элемент (один из них) оказался в левом верхнем углу.

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

12. Дан массив А, состоящий из n элементов. Осуществить перестановку элементов массива на M элементов вправо.

13. В двумерном массиве поменяйте местами первую строчку, и строчку в которой находится первый нулевой элемент.

14. В двумерном массиве переставьте строки следующим образом: первую с последней, вторую с предпоследней и так далее. Если строк нечетное число, то средняя остается неизмененной.

15. Дан двумерный массив А. Расставить его столбцы в следующем порядке:

а) последний, предпоследний,..., второй, первый;

б) первый, последний, второй, предпоследний, третий,...

16. Дан двумерный массив. Начиная с первой строки, сдвинуть все строки на две вниз, а последние перенести на место первых двух строк.

17. Дан двумерный массив вещественных чисел размерностью [1..N,1..N]. Произвести сортировку столбцов по убыванию элементов последней строки. Вычислить сумму элементов расположенных на диагоналях полученной матрицы. Сортировку произвести методом прямого выбора. Вывести на экран исходный и полученный массивы в виде матрицы.

18. Дан двумерный массив вещественных чисел размерностью [1..N,1..N]. Произвести сортировку столбцов по возрастанию элементов первой строки. Вычислить среднее арифметическое элементов расположенных по периметру полученной матрицы. Сортировку произвести методом прямого выбора. Вывести на экран исходный и полученный массивы в виде матрицы.

19. Дан двумерный массив, содержащий 4 строки и 5 столбцов. Элементами массива являются целые числа. Упорядочить массив по возрастанию элементов 3-го столбца.

20. Дан двумерный массив, содержащий 4 строки и 5 столбцов. Элементами массива являются целые числа. Упорядочить массив по убыванию элементов 2-й строки.

Приготовьте рабочие программы и листинги с задачами этой темы.

Строки