Побудова піраміди методом Флойда

1964 року Флойд запропонував метод побудови піраміди без явної побудови дерева (хоча метод заснований на тих самих ідеях). Побудова піраміди методом Флойда для нашого стандартного масиву показана в таблиці 7.

У таблиці 8 показано, як здійснюється сортування з використанням побудованої піраміди. Суть алгоритму полягає в подальшому. Нехай i – найбільший індекс масиву, для якого вказані умови піраміди. Тоді, починаючи з а[1] до а[і] виконуються такі дії.

Таблиця 8 – Сортування за допомогою піраміди.

На кожному кроці вибирається останній елемент піраміди (у нашому випадку першим буде вибраний елемент а[8]). Його значення міняється зі значенням а[1], після чого для а[1] виконується просіювання. При цьому на кожному кроці кількість елементів в піраміді зменшується на 1 (після першого кроку як елементи піраміди розглядаються а[1], а[2],..., а[n-1]; після другого – а[1], а[2],..., а[n-2] і т.ін., поки в піраміді не залишиться один елемент). Легко побачити (це ілюструється в таблиці 8), що як результат ми одержимо масив, впорядкований у порядку спадання. Можна модифікувати метод побудови піраміди і сортування, щоб одержати впорядкування у порядку зростання, якщо змінити умову піраміди а [і]>=а[2і] і а[1]>=а[2i+1] для всіх значень індекса i.

Процедура сортування з використанням піраміди вимагає виконання порядку nlog₂n кроків у гіршому разі, що робить її особливо привабливою для сортування великих масивів.

Сортування злиттям, як правило, застосовуються в тих випадках, коли вимагається відсортувати послідовний файл, що не вміщауться в основній пам'яті.

Нехай є два відсортованих у порядку зростання масиви р[1], р[2],...,р[n] і q[1],q[2],..., q[n] і є порожній масив r[1], r[2],..., r[2*n], який ми хочемо заповнити значеннями масивів p і q у порядку зростання. Для злиття виконуються такі дії: порівнюються р[1] і q [1], і менше зі значень записується в r[1]. Припустимо, що це значення р[1 ]. Тоді р[2] порівнюється з q[1], і менше із значень записується в r[2]. Припустимо, що це значення q[1]. Тоді на наступному кроці порівнюються значення р[2] і q[2] і т.ін., поки ми не досягнемо меж одного з масивів. Тоді залишок іншого масиву просто дописувається в ≪хвіст≫ масиву r.

Алгоритм сортуванням злиттям подано на рисунку 33.

Для випадку масиву, що використовується в наших прикладах, послідовність кроків показана в таблиці 9.

При застосуванні сортування зі злиттям кількість порівнянь ключів і кількість пересилань оцінюється як Θ (n*log n). Але слід врахо-вувати, що для виконання алгоритму для сортування масиву розміру n потрібно 2n елементів пам'яті.

Рисунок 33 – Блок-схема методу сортування злиттям.

Тема: Алгоритми сортування: методи зовнішнього сортування

Ціль: розглянути методи зовнішнього сортування та їх застосування

Прийнято називати ≪зовнішнім≫ сортування послідовних файлів, розташованих у зовнішній пам'яті і дуже великих, щоб можна було повністю перемістити їх в основну пам'ять і застосувати один з розглянутих у попередньому розділі методів внутрішнього сортування. Найчастіше зовнішнє сортування застосовується в системах керування базами даних при виконанні запитів, і від ефективності вживаних методів істотно залежить продуктивність СУБД.

Мусимо пояснити, чому йдеться саме про послідовні файли, тобто про файли, які можна читати запис за записом в послідовному режимі, а писати можна тільки після останнього запису. Методи зовнішнього сортування з'явилися, коли найбільш поширеними пристроями зовнішньої пам'яті були магнітні стрічки. Для стрічок послідовний доступ був абсолютно природним. Коли відбувся перехід до пристроїв, що запам'ятовують, з магнітними дисками, що забезпечують ≪прямий≫ доступ до будь-якого блоку інформації, здавалося, що послідовні файли втратили свою актуальність.Проте це припущення було помилковим.

Вся річ у тому, що практично всі використовувані на сьогодні дискові пристрої забезпечені рухомими магнітними головками. При виконанні обміну з дисковим накопичувачем виконується підведення головок до потрібного циліндра, вибір потрібної головки (доріжки), прокручування дискового пакету до початку необхідного блоку і,нарешті, читання або запис блоку. Серед всіх цих дій найбільший час займає підведення головок. Саме цей час визначає загальний час виконання операції. Єдиним доступним прийомом оптимізації доступу до магнітних дисків є якомога ≪ближче≫ розташування файла на накопичувачіблоків, що послідовно адресуються. Але і в цьому випадку рух головок буде мінімізованим у тому випадку, коли файл читається або пишеться в послідовному режимі. Саме з такими файлами при потребі сортування працюють сучасні СУБД.

Зазначимо, що насправді швидкість виконання зовнішнього сортування залежить від розміру буферу (або буферів) основної пам'яті, яка може бути використана для цих цілей.

Припустимо, що є послідовний файл А, що складається з записів а1,a2,…,an (знову для простоти припустимо, що n є ступенем числа 2). Вважатимемо, що кожен запис складається лише з одного елементу, що є ключем сортування. Для сортування використовуються два допоміжні файли В і С (розмір кожного з них буде n/2).

Сортування складаєтся з послідовності кроків, в кожному з яких виконується розподіл стану файлу А у файли В і С, а потім злиття файлів В і С у файл А. (Помітимо, що процедура злиття для файлів ілюструється рисунком 33). На першому кроці для розподілу послідовно читається файл А, і записи а1, а3, …, а (n-1) пишуться у файл В, а записи а2, а4, …, аn – у файл С (початковий розподіл). Початкове злиття здійснюється над парами (а1,а2), (а3,а4), …, (а(n-1),аn), ш результат записується у файл А. На другому кроці знову послідовно читається файл А, і у файл В записуються послідовні пари з непарними номерами, а у файл С – з парними. При злитті утворюються і пишуться у файл А впорядковані четвірки записів. І так далі. Перед виконанням останнього кроку файл А міститиме дві впорядковані послідовності розміром n/2 кожна. При розподілі перша з них потрапить у файл В, а друга – у файл С. Після злиття файл А міститиме повність впорядковану послідовність записів. У таблиці 10 показаний приклад зовнішнього сортування простим злиттям. Заз начимо, що для виконання зовнішнього сортування методом простого злиття в основній памяті вимагається розташувати всього дві змінні – для розміщення записів з файлів В і С.

Таблиця 10 – Приклад зовнішнього сортування простим злиттям

При використанні методу прямого злиття не береться до уваги те, що початковий файл може бути частково відсортованим, тобто містити впорядковані підпослідовності записів.

Серією називається підпослідовність записів аі, а(i+1),..., aj така, що ak<=a(k+1) для всіх i<= k<j, аі < а(і-1) і aj>a(j+1). Метод природного злиття ґрунтується на розпізнаванні серій при розподілі і їх використанні при подальшому злитті.

Як і у разі прямого злиття, сортування виконується за декілька кроків, в кожному з яких спочатку виконується розподіл файла А по файлам В і С, а потім злиття В і С у файл А. При розподілі розпізнається перша серія записів і переписується у файл В, друга - у файл С і т.ін. При злитті перша серія записів файлу В зливається з першою серією файлу С, друга серія В з другою серією С і т.ін. Якщо перегляд одного файлу закінчується раніше, ніж перегляд іншого (внаслідок різної кількості серій), то залишок не до кінця переглянутого файла повністю копіюється в кінець файла А. Процес завершується, коли у файлі А залишається тільки одна серія. Приклад сортування файла показаний на рисунках 34 і 35.

Рисунок 34 – Зовнішнє пряме сортування злиттям. Перший крок.

Рисунок 35 – Зовнішнє пряме сортування злиттям. Другий крок.

Очевидно, що кількість зчитувань/перезаписів файлів при використанні цього методу буде не більша, ніж при застосуванні методу прямого злиття, а в середньому – менша. З другого боку, збільшується кількість порівнянь за рахунок тих, які потрібні для розпізнавання кінців серій. Крім того, оскільки довжина серій може бути довільною, то максимальний розмір файлів В і С може бути близький до розміру файла А.

Что вызывает тренды на фондовых и товарных рынках Объяснение теории грузового поезда Первые 17 лет моих рыночных исследований сводились к попыткам вычислить, когда этот...

Живите по правилу: МАЛО ЛИ ЧТО НА СВЕТЕ СУЩЕСТВУЕТ? Я неслучайно подчеркиваю, что место в голове ограничено, а информации вокруг много, и что ваше право...

ЧТО ПРОИСХОДИТ ВО ВЗРОСЛОЙ ЖИЗНИ? Если вы все еще «неправильно» связаны с матерью, вы избегаете отделения и независимого взрослого существования...

Конфликты в семейной жизни. Как это изменить? Редкий брак и взаимоотношения существуют без конфликтов и напряженности. Через это проходят все...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: