Быстрые алгоритмы сортировки
Категория реферата: Рефераты по информатике, программированию
Теги реферата: реферат государственный, реферат по математике
Добавил(а) на сайт: Бальсунов.
Предыдущая страница реферата | 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 | Следующая страница реферата