Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Рассмотрим использование рекурсии для построения алгоритма сортировки значений массива.
Алгоритм реализуется следующим образом: в некотором отрезке массива выбирается центральное (серединное) значение; все элементы из левой части отрезка, превосходящие центральное значение, перемещаются в правую часть, и наоборот. На следующем шаге (для которого используются рекурсивные вызовы этой же процедуры) алгоритм повторяется для обоих частей отрезка.
Рассмотрите процедуру, упорядочивающую по возрастанию значения из массива 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; |
Задача. Составьте программу, реализующую рассмотренный метод. Дополните ее комментариями.
Сортировка методом слияний.
Определение. Целочисленный массив с расположенными по неубыванию или по невозрастанию значениями элементов называется упорядоченным.
Использование упорядоченности позволяет создавать эффективные алгоритмы для решения многих интересных задач.
Задача слияния двух входных упорядоченных массивов А и В состоит в формировании упорядоченного выходного массива С, содержащего все элементы из входных массивов.
Рассмотрим алгоритм слияния для упорядоченных по неубыванию массивов. Вначале элемент А[1] сравнивается с элементом В[1] и наименьший из них записывается в массив С. Если наименьшим был А[1], то на следующем шаге сравниваются А[2] и B[1], а если наименьшим был B[1], то будут сравниваться A[1] и B[2] и т.д. Если на очередном шаге окажется, что из одного входного массива все элементы переписаны в С, то переписывается элемент из другого массива.
Рассмотрим пример работы алгоритма слияния.
Пусть в массиве А содержатся 3 элемента: {5, 13, 14}, а в массиве В - 4 элемента: {7, 9, 10, 12}. Внимательно рассмотрите таблицу, в которой по шагам показано изменение переменных i, i1, i2 и действия с массивами.
Рассмотрите фрагмент решения задачи на слияние двух массивов А и В, которые содержат соответственно 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.
Предположив, что Вы правильно выполнили предыдущую задачу, алгоритм сортировки можно определить очень просто:
Рассмотрите процедуру сортировки слиянием. На вход процедуры сортировки поступает неупорядоченный кусок массива А с номерами элементов от 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; |
Самостоятельное решение задач.
Задание. Выберите с учителем задачи для решения из предложенного ниже перечня.
Приготовьте рабочие программы и листинги с задачами этой темы.
Дата публикования: 2015-10-09; Прочитано: 1128 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!