ри операції пересилки. br/>
Пірамідальна сортування
Пірамідальна сортування (англ. Heapsort, В«Сортування купоюВ») - алгоритм сортування, що працює в гіршому, в середньому і в кращому випадку (тобто гарантовано) за ? ( n log n) операцій при сортуванні n елементів. Кількість застосовуваної службової пам'яті не залежить від розміру масиву (тобто, O (1)).
Ідея алгоритму
Піраміда - двійкове дерево, в якому значення кожного елемента більше або дорівнює значень дочірніх елементів.
Заповнивши дерево елементами в довільному порядку, можна легко його впорядкувати (легше, ніж вихідний список елементів), перетворивши в піраміду.
Найбільший елемент піраміди знаходиться в її вершині.
Відділяємо вершинний елемент, і записуємо його в кінець результуючого масиву.
На місце вершинного елемента записуємо елемент з самого нижнього рівня дерева.
Відновлюємо (перевпорядковувати) піраміду.
Найбільший елемент з решти знову в вершині. Знову відокремлюємо його і записуємо його в якості передостаннього елемента результату, і так далі ...
Весь фокус алгоритму в тому, що піраміда без додаткових витрат зберігається прямо в результат ном масиві. У міру того, як розмір піраміди зменшується, вона займає все меншу частину масиву, а результат сортування записується починаючи з кінця масиву на звільнивши шіеся від піраміди місця.
Переваги і недоліки
Переваги
. Має доведену оцінку гіршого випадку.
. Вимагає всього O (1) додаткової пам'яті (якщо дерево організовувати так, як показано вище).
Недоліки
. Складний в реалізації.
. Нестійкий - для забезпечення стійкості потрібно розширювати ключ.
. На майже відсортованих масивах працює так само довго, як і на хаотичних даних.
. На одному кроці вибірку доводиться робити хаотично по всій довжині масиву - тому алгоритм погано поєднується з кешуванням і підкачкою пам'яті.
Через складність алгоритму виграш виходить тільки на великих n. На невеликих n (до декількох тисяч) швидше сортування Шелла. br/>
Технологічний розділ
Блок-схема програми
В
У курсовій роботі використовувалися такі стандартні заголовні файли:
- заголовний файл з класами, функціями і змінними для організації введення-виведення в мові програмування C + +. Він включений в стандартну бібліотеку C + +. Назва утво...
