double arrow

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

Задача. Напишите программу, содержащую алгоритм слияния в процедуре 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;


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: