Пірамідальне сортування

Цей метод опирається на пірамідальну структуру дерева. Він скла­дається з двох частин - побудови піраміди (алгоритм Р) і безпосе­редньо сортування (алгоритмF).

Послідовність ключів K₁, К₂... К _n називають "пірамідою", якщо K_j < K_i при 2<j<n. i =[ j /2] - ціла частина від j/2.

Бінарне дерево розміщується послідовно таким чином, що індекси лівого і правого "синів" запису будуть мати відповідно значення 2і і 2і+1. Навпаки, індекс "батька" запису буде мати значення [j/2]. Якщо знайдено пірамідальне зображення таблиці, то запис з найбільшим ключем знаходиться в корені дерева.

На вхід алгоритму Р подається невідсортована послідовно розміще­на таблиця, а на виході - утворюється піраміда. Початковим моментом у роботі алгоритму Р є побудова піраміди, яка на початку складається з одного запису. Потім в неї послідовно вставляються чергові записи, поки не вичерпаються всі записи вхідної таблиці і в результаті чого сформується піраміда.

В алгоритмі Р використані такі позначення: вхідна таблиця R містить п записів R₁,..., R_n; індексна змінна q служить для керування кількістю виконаних вставок; змінна і єіндексом "батька" запису R_j; NEW - робоча область для запису; KEY містить ключ запису, який у даний момент повинен бути вставлений у наявну піраміду.

Алгоритм Р побудови піраміди.

Р1. Побудова піраміди. Повторювати кроки Р2 –Р6 при q=2,3,4,...,n.

P2. Ініціалізація: встановити j=q, NEW= R_q.; KEY = K_q.

P3. Вставка нового запису в наявну піраміду. Повторювати кроки Р4, Р5 доти, доки і>1.

Р4. Знаходження "батька" нового запису: встановити і=[j/2].

Р5. Перестановка записів: якщо KEY > K_i, товстановити R_i = R_j, i=j, інакше перейти до кроку Р6.

Р6. Копіювання нового запису у відповідне місце: встановити R_j =NEW.

P7. Кінець. Вихід.

Перший крок алгоритму - оператор, що повторюється. Він керує по­будовою потрібної піраміди, послідовно вставляючи нові записи. У кро­ці Р2 вибирається запис, який повинен бути встановлений у наявну пі­раміду, і виконується копіюванням цього запису в область NEW. У кроках Р4 і Р5 новий запис приєднується /у вигляді листка/ до наявної піраміди /тобто до бінарного дерева/ і просувається на дереві по шляху між новим листком і вершиною піраміди. Цей процес повторюється доти, доки новий запис не досягне в дереві позиції, що задовольняє визначенню піраміди. Копіювання нового запису у відповідне йому місце в дереві виконується у кроці Р6.

Безпосередньо сортування наявної піраміди зводиться до багато­разового виключення вершини піраміди і подальшої її реконструкції - запису цієї вершини на своє остаточне місце. Алгоритм сортування ви­користовує алгоритм Р - алгоритм побудови піраміди.

Алгоритм F сортування з використанням алгоритму Р- алгоритм Флойда.

Нехай задана таблиця R, що містить n записів R₁,..., R_n, i алгоритм побудови піраміди P. Цей алгоритм здійснює сортування таблиці у зростаючому порядку. Змінна q є індексом обходу дерева. Індексні змінні і,j, викорис­товуються у тому випадку, коли j є індексом лівого "сина" запису з ключем К_i; SAVE - робоча область зберігання запису; KEY - змін­на, що містить ключ запису при кожному проходженні; і - індекc вершини - "батька".

Алгоритм F по кроках.

Fl. Побудова піраміди: виклик програми Р.

F2. Виконання сортування: повторювати кроки F2 - F8 при q=n,n-1,…,2.

F3. Локалізація запису з iндексом q: встановити R₁= R_q.

F4. Ініціалізація індексів: встановити i=1,, SAVE= R1,KEY=k1, j=2.

F5. Реконструкція піраміди: повторювати кроки F6, F 7 доки j<q-1.

F6. Одержання iндексa "сина" з найбільшим значенням ключа:

якщо j+1<q, K_j+1 > K_j, встановити j=j+1.

F7. Чи потрібна перестановка записів? Якщо K_j > KEY, то вста­новити R_i= R_j, i=j, j=2*I; Інакше перейти на крок F8.

F8. Копіювання запису на відповідне місце: встановити R_i=SAVE.

F9. Кінець: вихід.

Робота даного алгоритму починається з побудови піраміди для вхід­ної таблиці. Крок F2 здійснює керування n-1 проходженням всієї таблиці, необхідним для її сортування, інші кроки аналогічні крокам алгоритму Р для побудови нової піраміди після включення нового запису. Ця аналогія полягає у тому, що вершина R₁ піраміди помі­няється місцями з вершиною R_n, а потім нова піраміда, що містить n-1 записів, реконструюється за допомогою програми Р. Результа­том такої реконструкції є розміщення запису з другим найбільшим зна­ченням ключа у вершині R₁. Цей запис поміняється місцями із записом R_n-1, і будується нова піраміда, що містить n-2 записи, і т.д.

Аналіз найгіршого випадку для цього алгоритму показав, що число порівнянь, які потрібно виконати, дорівнює величині порядку О(п log₂ n). Крім того, для даного алгоритму непотрібно додаткових робочих областей пам‘яті, за виключенням поля для одного запису.

Отже, розглянуто велику кількість різних методів сортування. Кращі методи потребують порядку п log₂ n порівнянь, найпростіші - поряд­ку n². Методи сортування з обчисленням адреси і числове або цифрове сортування використовують додаткову інформацію про дані і вимагають n порівнянь. Кращі методи сортування не вимагають додаткової пам‘яті, крім тієї, яка потрібна для зберігання даних, програми і фіксовано­го набору керуючих величин. Багато методів сортування використовують додаткову пам‘ять обсягом порядку log₂ n або n квантів.

При виборі методу сортування необхідно враховувати структуру даних, вимоги до часу і обсягу пам‘яті, а також складність програмування ал­горитму.