Зміст
Зміст
Постановка Задачі
Теоретичні Відомості
Вхідні - Вихідні дані
математичних розв'язок
Схема алгоритму Програми
Алгоритм процедури введення даніх
Алгоритм процедури виведення результатів сортування
Алгоритм процедури Побудова дерева
Алгоритм процедури перестановки елементів
Алгоритм процедури В«Вирішення сімейного конфліктуВ»
Контрольний приклад для масивов з 20 елементів
Побудова Піраміди
Сортування
Опіс використаних в реалізації методу процедур та функцій
Корістувацьке Вікно (форма)
Текст Програми
Список використаної літератури
Постановка Задачі
Відсортуваті масив з 20 елементів, вікорістовуючі пірамідальне сортування.
Теоретичні Відомості
Сортування даніх - Ції обробка інформації, в результаті якої її Елементи розташовуються в заданій послідовності, в залежності від Значення Деяк ознайо елементів цієї інформації.
Найбільш Поширення видом сортування є впорядкування масива.
Задача сортування полягає в перестановці елементів послідовності в визначеному порядку. Впорядкування здійснюється в процесі багаторазове Перегляд вхідного масива. Методи сортування діляться на два класи:
1) Внутрішнє сортування, коли Працюють з данімі в оператівній пам'яті з довільнім доступом;
2) Зовнішнє сортування, коли впорядковують інформацію, розташовану на зовнішніх носіях.
Алгоритм пірамідального сортування HeapSort вікорістовує представлені масивов у віді дерева. Цей алгоритм не вімагає допоміжніх масівів, сортуючі "на місці". Розглянемо Спочатку метод представлення масиву у віді дерева:
Нехай A [1 .. n] - Деяк масив. Зіставімо йому дерево, вікорістовуючі наступні правила:
1. A [1] - корінь дерева;
2. ЯКЩО A [i] - вузол дерева и 2i, то A [2 * i] - вузол - "Лівий сін" вузла A [i]
3. ЯКЩО A [i] - вузол дерева и 2i + 1, то A [2 * i +1] - вузол - "правий син" вузла A [i]
Правила 1-3 визначаються у масіві структуру дерева, причому Глибина дерева не перевершує [Log2 n] + 1. Смороду ж задають спосіб руху по дереву від кореня до листків. Рух вгору задається правилом 4:
4. ЯКЩО A [i] - вузол дерева та i> 1, то A [i mod 2] - вузол - "батько" вузла A [i];
Вхідні - Вихідні дані
Для роботи з даною программа та алгоритму пірамідального сортування взагалі, нам необхідно ввести Елементи масивов візначеної довжина, Який необхідно відсортуваті.
В результаті роботи Програми мі отрімаємо відсортованій масив введених елементів.
Вхідні дані
Вихідні дані
Розмір вхідного масиву В«NВ»
Масив з В«NВ» елементів, елементи - цілі числа (Масив A [1 .. N] - невпорядкованій).
впорядкованим масив з В«NВ» елементів, елементи - цілі числа, Коженов елемент масива Більше або дорівнює Попередня (Масив A [1 .. N]; A [i] <= A [i +1]).
Математичний розв'язок
Алгоритм пірамідального сортування працює в два етапи:
I. Побудова сортуючого дерева;
II. Просіювання елементів по сортуючому дереву.
Як на I-ому, так и на II-ому етапах елементарних дія алгоритму полягає в вірішенні сімейного конфлікту: Якщо найбільшій Із Синів Більше, Ніж батьку, то переставляються батьку и цею сін (процедура Swap).
У результаті перестановки Може вінікнуті новий Конфлікт у тому трикутнику, Куди переставлених батьку. У такий спосіб можна Говорити про Конфлікт (роду) у піддереві з коренем у вершіні i. Конфлікт роду вірішується послідовнім вірішенням сімейних конфліктів проходом по дереву вниз. Конфлікт роду вірішено, ЯКЩО прохід закінчівся (i> n div 2), або ж в результаті перестановки не виник новий сімейний Конфлікт (процедура Conflict).
I етап - побудова сортуючого дерева - оформімо у віді рекурсівної процедури, вікорістовуючі визначення:
ЯКЩО ліве и право піддерева (T [2i] и T [2i +1]) дерева T [i] є сортуючімі, то для перебудови T [i] необхідно вірішіті Конфлікт роду в цьому дереві.
II етап - етап просіювання - для k від n до 2 повторюються наступні дії:
1.Переставіті A [1] и A [k];
2.Побудуваті сортуюче дерево Початкова відрізка масиву A [1 .. k-1], усунувші Конфлікт роду в корені A [1]. Відзначімо, Що 2-а дія вімагає Введення в процедуру Conflict параметра k.
Недоладно підрахуваті, Що З (n) = O (n log2 n), М (n) = O (n log2 n)
Схема алгоритму Програми
Алгоритм процедури введення даніх
Алгоритм процедури виведення результатів сортування
Алгоритм процедури Побудова дерева
Алгоритм процедури перестановки елементів
b = a [i]
a [i] = a [j]
a [j] = b
Алгоритм процедури В«Вирішення сімейного конфліктуВ»
Контрольний приклад для масивов з 20 елементів
Побудова Піраміди
Сортування
алгоритм программа елемент Вікно
Опіс використаних в реалізації методу процедур та функцій
Процедура Swap
Procedure Swap (i, j: Integer)
Переставляє місцямі Елементи масиву A [i] та A [j] за умов, ЯКЩО A [i]
Процедура Conflict
Procedure Conflict (i, k: Integer)
Вірішує сімейний Конфлікт у дереві: Якщо найбільшій Із Синів Більше, Ніж батьку, то переставляються батько и цею сін (процедура Swap).
Процедура SortTree
Procedure SortTree (i: Integer)
Будує сортуюче дерево за правилами:
1. A [1] - корінь дерева;
2. ЯКЩО A [i] - вузол дерева и 2i, то A [2 * i] - вузол - "Лівий сін" вузла A [i]
3. ЯКЩО A [i] - вузол дерева и 2i + 1, то A [2 * i +1] - вузол - "правий син" вузла A [i]
Правила 1-3 визначаються у масіві структуру дерева, причому Глибина дерева не перевершує [Log2 n] + 1. Смороду ж задають спосіб руху по дереву від кореня до листків. Рух вгору задається правилом 4:
4. ЯКЩО A [i] - вузол дерева та i> 1, то A [i mod 2] - вузол - "батько" вузла A [i].
Процедура Show_result
Procedure Show_result
Віводіть в ціклі Елементи відсортованого масиву на екран.
Процедура get_data
Procedure get_data
Зчітує Значення елементів масива для сортування.
Корістувацьке Вікно (форма)
Текст Програми
var
Form1: TForm1;
A: array [1 .. 20] of real;
N, k: integer;
implementation
Procedure Swap (i, j: Integer);
Var b: Real;
Begin
If a [i]
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;
