Сортування на деревах

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

6.1.1. Метод вибірки з дерева /алгоритм Н /.

Послідовність чисел розбивається на пари, які об‘єднуються за принципом «син-батько». Батьком з двох синів стає найбільше число. Процес повторюється, доки не буде виділене одне число, найбільше, яке стане корнем утвореного дерева. У разі відсутності одного числа, батьком стає єдиний нащадок (син). Число, що попало в корінь замінюється на безмежність. Процес повторюється для знаходження наступного найбільшого числа і т.д. З рис. 6.1 видно, що задана послідовність буде впорядкована у низхід­ному порядку за 10-1=9 кроків.

Сумарний час виконання такого сортування приблизно пропорційний величині п log₂ n. Існує декілька модифікацій цього алгоритму, які скорочують цей час.

Рис.6.1. Схема сортування методом вибірки з дерева:

а - послідовність з десяти чисел для відбору першого найбільшого елемента;

б - вибір другого найбільшого елемента.

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

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

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