відбувається рух) встановлюються в місці останнього обміну на кожній ітерації. Масив проглядається по черзі справа наліво і зліва направо. p align="justify"> Кращий випадок для цієї сортування - відсортований масив (О (n)), найгірший - відсортований у зворотному порядку (O (n ВІ )). [1]
Пірамідальна - алгоритм сортування, що працює в гіршому, в середньому і в кращому випадку (тобто гарантовано) за ? (n log n) операцій при сортуванні n елементів. Кількість застосовуваної службової пам'яті не залежить від розміру масиву (тобто, O (1)). [1]
Може розглядатися як вдосконалена сортування бульбашкою, в якій елемент спливає (min-heap)/тоне (max-heap) за багатьма шляхами.
Сортування пірамідою використовує Сортувальне дерево. Сортувальне дерево - це таке двійкове дерево, у якого виконані умови:
1. Кожен лист має глибину або , або , - максимальна глибина дерева.
2. Значення в будь-якій вершині більше, ніж значення її нащадків.
Зручна структура даних для сортує дерева - такий масив Array, що Array [1] - елемент в корені, а нащадки елемента Array [i] - Array [2i] і Array [2i +1].
Алгоритм сортування буде складатися з двох основних кроків:
. Вибудовуємо елементи масиву у вигляді сортують дерева:
Array [i]? Array [2i] [i]? Array [2i +1], при n/2? i? 1. p align="justify"> Цей крок вимагає операцій.
. Будемо видаляти елементи з кореня по одному за раз і перебудовувати дерево. Тобто на першому кроці обмінюємо Array [1] і Array [n], перетворюємо Array [1], Array [2], ..., Array [n-1] в сортирі дерево. Затемпереставляем Array [1] і Array [n-1], перетворимо Array [1], Array [2], ..., Array [n-2] в сортирі дерево. Процес продовжується до тих пір, поки в сортирі дереві не залишиться один елемент. Тоді Array [1], Array [2], ..., Array [n] - упорядкована послідовність. [1] Цей крок вимагає операцій.
Вибір алгоритму сортування перестановками обумовлений його простотою і швидкодією в порівнянні з іншими описаними вище алгоритмами.
В основі алгоритму лежить обмін сусідніх елементів масиву. Кожен елемент масиву, починаючи з першого, порівнюється з наступним, і якщо він більше наступного, то елементи міняються місцями. Таким чином, елементи з меншим значенням просуваються до початку масиву (спливають), а елементи з великим значе...
