Швидкі алгоритми сортування, Детальна інформація

Швидкі алгоритми сортування
Тип документу: Реферат
Сторінок: 15
Предмет: Комп`ютерні науки
Автор: Олексій
Розмір: 29.4
Скачувань: 1298
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;

{ виведення }

The online video editor trusted by teams to make professional video in minutes