Швидкі алгоритми сортування, Детальна інформація
Швидкі алгоритми сортування
2.Якщо A[i] - вузол дерева і 2i ( n,
то A[2*i] - вузол - “лівий син” вузла A[i]
3.Якщо A[i] - вузол дерева і 2i + 1 ( n,
то A[2*i+1] - вузол - “правий син” вузла A[i]
Правила 1-3 визначають у масиві структуру дерева, причому глибина дерева не перевершує [log2 n] + 1. Вони ж задають спосіб руху по дереву від кореня до листків. Рух вгору задається правилом 4:
4.Якщо A[i] - вузол дерева і i > 1,
то A[i mod 2] - вузол - “батько” вузла A[i];
Приклад: Нехай A = [45 13 24 31 11 28 49 40 19 27] - масив. Відповідне йому дерево має вид:
Зверніть увагу на те, що всі рівні дерева, за винятком останнього, цілком заповнені, останній рівень заповнений ліворуч і індексація елементів масиву здійснюється вниз і праворуч. Тому дерево упорядкованого масиву відповідає наступним властивостям:
A[i] ( A[2*i], A[i] ( A[2*i+1], A[2*i] ( A[2*i+1].
Як це не дивно, алгоритм HeapSort спочатку будує дерево, що відповідає прямо протилежним співвідношенням:
A[i] ( A[2*i], A[i] ( A[2*i+1]
а потім змінює місцями A[1] (найбільший елемент) і A[n].
Як і TreeSort, алгоритм HeapSort працює в два етапи:
I. Побудова сортуючого дерева;
II. Просівання елементів по сортуючому дереву.
Дерево, що представляє масив, називається сортуючим, якщо виконуються умови (6). Якщо для деякого i ця умова не виконується, будемо говорити, що має місце (сімейний) конфлікт у трикутнику i.
Як на I-ом, так і на II-ому етапах елементарна дія алгоритму полягає в вирішенні сімейного конфлікту: якщо найбільший із синів більше, ніж батько, то переставляються батько і цей син (процедура ConSwap).
У результаті перестановки може виникнути новий конфлікт у тому трикутнику, куди переставлений батько. У такий спосіб можна говорити про конфлікт (роду) у піддереві з коренем у вершині i. Конфлікт роду вирішується послідовним вирішенням сімейних конфліктів проходом по дереву вниз. (На мал шлях вирішення конфлікту роду у вершині 2 відзначений). Конфлікт роду вирішено, якщо прохід закінчився (i > n div 2), або ж в результаті перестановки не виник новий сімейний конфлікт (процедура Conflict).
Procedure ConSwap(i, j : Integer);
Var b : Real;
Begin
If a[i] < a[j] then begin
b := a[i]; a[i] := a[j]; a[j] := b
end
End;
Procedure Conflict(i, k : Integer);
Var j : Integer;
Begin
j := 2*i;
то A[2*i] - вузол - “лівий син” вузла A[i]
3.Якщо A[i] - вузол дерева і 2i + 1 ( n,
то A[2*i+1] - вузол - “правий син” вузла A[i]
Правила 1-3 визначають у масиві структуру дерева, причому глибина дерева не перевершує [log2 n] + 1. Вони ж задають спосіб руху по дереву від кореня до листків. Рух вгору задається правилом 4:
4.Якщо A[i] - вузол дерева і i > 1,
то A[i mod 2] - вузол - “батько” вузла A[i];
Приклад: Нехай A = [45 13 24 31 11 28 49 40 19 27] - масив. Відповідне йому дерево має вид:
Зверніть увагу на те, що всі рівні дерева, за винятком останнього, цілком заповнені, останній рівень заповнений ліворуч і індексація елементів масиву здійснюється вниз і праворуч. Тому дерево упорядкованого масиву відповідає наступним властивостям:
A[i] ( A[2*i], A[i] ( A[2*i+1], A[2*i] ( A[2*i+1].
Як це не дивно, алгоритм HeapSort спочатку будує дерево, що відповідає прямо протилежним співвідношенням:
A[i] ( A[2*i], A[i] ( A[2*i+1]
а потім змінює місцями A[1] (найбільший елемент) і A[n].
Як і TreeSort, алгоритм HeapSort працює в два етапи:
I. Побудова сортуючого дерева;
II. Просівання елементів по сортуючому дереву.
Дерево, що представляє масив, називається сортуючим, якщо виконуються умови (6). Якщо для деякого i ця умова не виконується, будемо говорити, що має місце (сімейний) конфлікт у трикутнику i.
Як на I-ом, так і на II-ому етапах елементарна дія алгоритму полягає в вирішенні сімейного конфлікту: якщо найбільший із синів більше, ніж батько, то переставляються батько і цей син (процедура ConSwap).
У результаті перестановки може виникнути новий конфлікт у тому трикутнику, куди переставлений батько. У такий спосіб можна говорити про конфлікт (роду) у піддереві з коренем у вершині i. Конфлікт роду вирішується послідовним вирішенням сімейних конфліктів проходом по дереву вниз. (На мал шлях вирішення конфлікту роду у вершині 2 відзначений). Конфлікт роду вирішено, якщо прохід закінчився (i > n div 2), або ж в результаті перестановки не виник новий сімейний конфлікт (процедура Conflict).
Procedure ConSwap(i, j : Integer);
Var b : Real;
Begin
If a[i] < a[j] then begin
b := a[i]; a[i] := a[j]; a[j] := b
end
End;
Procedure Conflict(i, k : Integer);
Var j : Integer;
Begin
j := 2*i;
The online video editor trusted by teams to make professional video in
minutes
© Referats, Inc · All rights reserved 2021