Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата



Begin j := 2*i;

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

End;

I етап – побудова сортуючого дерева - оформимо у виді рекурсивної процедури, використовуючи визначення:

Якщо ліве і праве піддерева T(2i) і T(2i+1) дерева T(i) є сортуючими, то для перебудови T(i) необхідно вирішити конфлікт роду в цьому дереві.

Procedure SortTree(i : Integer); begin

If i j , причому на поділ ми затратимо не більш n/2 перестановок. Тепер залишилося проробити ті ж дії з початком і кінцем масиву, тобто застосувати їх рекурсивно.

Таким чином, описана нами процедура Hoare залежить від параметрів k та m - початкового і кінцевого індексів відрізка масиву, який обробляється.

Procedure Swap(i, j : Integer);

Var b : Real;

Begin b := a[i]; a[i] := a[j]; a[j] := b

End;

Procedure Hoare(L, R : Integer);

Var left, right : Integer; x : Integer;

Begin

If L < R then begin x := A[(L + R) div 2]; {вибір бар'єра x} left := L; right := R ;

Repeat {зустрічний прохід}

While A[left] < x do Inc(left); {перегляд уперед}

While A[right] > x do Dec(right); {перегляд назад}

If left right;

Hoare(L, right); {сортуємо початок}

Hoare(left, R) {сортуємо кінець} end

End;

Program QuickSort;

Рекомендуем скачать другие рефераты по теме: ответы 11 класс, скачать контрольные работы.

Предыдущая страница реферата | 1  2  3  4  5  6  7  8  9 | Следующая страница реферата