Швидкі алгоритми сортування, Детальна інформація
Швидкі алгоритми сортування
If j = k
then ConSwap(i, j)
else if j < k then begin
if a[j+1] > a[j] then j := j + 1;
ConSwap(i, j); Conflict(j, k)
end
††\x4520\x646E\x0D3B
I етап – побудова сортуючого дерева - оформимо у виді рекурсивної процедури, використовуючи визначення:
Якщо ліве і праве піддерева T(2i) і T(2i+1) дерева T(i) є сортуючими, то для перебудови T(i) необхідно вирішити конфлікт роду в цьому дереві.
Procedure SortTree(i : Integer);
begin
If i <= n div 2 then begin
SortTree(2*i); SortTree(2*i+1); Conflict(i, n)
end
end;
На II-ом етапі - етапі просівання - для k від n до 2 повторюються наступні дії:
1.Переставити A[1] і A[k];
2.Побудувати сортуюче дерево початкового відрізка масиву A[1..k-1], усунувши конфлікт роду в корені A[1]. Відзначимо, що 2-а дія вимагає введення в процедуру Conflict параметра k.
Program HeapSort;
Const n = 100;
Var A : Array[1..n] of real;
k : Integer;
{процедури ConSwap, Conflict, SortTree, введення, виведення}
Begin
{ введення }
SortTree(1);
For k := n downto 2 do begin
ConSwap(k, 1); Conflict(1, k - 1)
end;
{ виведення }
then ConSwap(i, j)
else if j < k then begin
if a[j+1] > a[j] then j := j + 1;
ConSwap(i, j); Conflict(j, k)
end
††\x4520\x646E\x0D3B
I етап – побудова сортуючого дерева - оформимо у виді рекурсивної процедури, використовуючи визначення:
Якщо ліве і праве піддерева T(2i) і T(2i+1) дерева T(i) є сортуючими, то для перебудови T(i) необхідно вирішити конфлікт роду в цьому дереві.
Procedure SortTree(i : Integer);
begin
If i <= n div 2 then begin
SortTree(2*i); SortTree(2*i+1); Conflict(i, n)
end
end;
На II-ом етапі - етапі просівання - для k від n до 2 повторюються наступні дії:
1.Переставити A[1] і A[k];
2.Побудувати сортуюче дерево початкового відрізка масиву A[1..k-1], усунувши конфлікт роду в корені A[1]. Відзначимо, що 2-а дія вимагає введення в процедуру Conflict параметра k.
Program HeapSort;
Const n = 100;
Var A : Array[1..n] of real;
k : Integer;
{процедури ConSwap, Conflict, SortTree, введення, виведення}
Begin
{ введення }
SortTree(1);
For k := n downto 2 do begin
ConSwap(k, 1); Conflict(1, k - 1)
end;
{ виведення }
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021