Сортировка методом слияний Рекурсивная сортировка методом слияний. - презентация

1 Сортировка методом слияний Рекурсивная сортировка методом слияний

2 Сортировка методом слияний Определение. Целочисленный массив с расположенными по неубыванию или по невозрастанию значениями элементов называется упорядоченным. Использование упорядоченности позволяет создавать эффективные алгоритмы для решения многих интересных задач. Пример: Задача слияния двух входных упорядоченных массивов А и В состоит в формировании упорядоченного выходного массива С, содержащего все элементы из входных массивов.

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

4 Работа алгоритма для A=[5,13,14] B=[7,9,10,12]

5 Фрагмент программы... 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;...

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

7 Составим алгоритм сортировки если длина сортируемого массива 1, то ничего не делается; в противном случае массив делится на две одинаковые (или почти одинаковые) части, к каждой части применяется алгоритм сортировки, после чего эти упорядоченные части сливаются в один упорядоченный кусок. На вход процедуры сортировки поступает неупорядоченный кусок массива А с номерами элементов от b до e, на выходе - тот же кусок, но упорядоченный.

8 Исходный код процедуры Procedure Sort2(Var A, C : Array1; b, e : integer); Var i, d : integer; BEGIN If b

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