WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Демонстрація сортування методом спливаючих бульбашок - Курсова робота

Демонстрація сортування методом спливаючих бульбашок - Курсова робота

методом прямого включення, як і всі описані вище, проводиться по кроках. На к-м кроці вважається, що частина масиву, що містить перші k-1 елементів, вже впорядкована, тобто а[1]< а[2]< . . . < а[к-l]. Далі необхідно узяти k-й елемент і підібрати для нього таке місце у відсортованій частині масиву, щоб після його вставки впорядкованість не порушилася, тобто треба знайти таке j (1<=j<=k-1), що а[j ]<=a[k] .
1.4. Складніші і більш ефективні методи сортування.
При рішенні складніших задач доводиться обробляти великі набори даних. Застосування простих для розуміння, але повільно працюючих методів сортування, висловлених в попередньому розділі, стає недоцільно.
Обмінне сортування з розділенням (сортування Хоара) .
Сортування методом простого обміну (методом "бульбашки") є в середньому найефективнішим. Це обумовлено самою ідеєю методу, який вимагає в процесі сортування порівнювати і обмінювати між собою тільки сусідні елементи. Можна істотно поліпшити метод сортування, заснований на обміні. Це поліпшення приводить до найкращому методу сортування масивів, який можна назвати обмінним сортуванням з розділенням. Він заснований на порівняннях і обмінах елементів, що стоять на можливо великих відстанях один від одного. Запропонував цей метод Ч. А. Р. Хоар в 1962 році. Оскільки продуктивність цього методу вражаюча, автор назвав його "швидким сортуванням".
Сортування методом злиття.
Існує ще один метод сортування елементів масиву, ефективність якого порівняно велика, - метод злиття. Метод сортування "злиттям" полягає в розбитті даного масиву на декілька частин, які сортуються по окремості і згодом "зливаються" в одну. Хай масив а [1..n] розбивається на частини завдовжки k, тоді перша частина - а[I], а [2] . . ., а [k], друга [k+l], а[k+2]..., а[2k] і так далі. Якщо n не ділиться на k, то в останній частині буде менш k елементів. Після того, як масиви-частини впорядковані, можна об'єднати їх у впорядковані масиви-частини, які складаються з не більше ніж з 2k елементів, які далі об'єднуються у впорядковані масиви завдовжки не більш 4k,і так далі поки не вийде один впорядкований масив. Так, щоб отримати відсортований масив цим методом, потрібно багато разів " зливати" два впорядковані відрізки масиву в один впорядкований відрізок. При цьому інші частини масиву не зачіпаються.
Сортування методом Шелла
Ідея алгоритму полягає в обміні елементів, розташованих не тільки поряд, як в сортуванні методом вставок, але і далеко один від одного, що значно скорочує загальне число операцій переміщення елементів.
Для прикладу візьмемо масив з 16 елементів. Спочатку продивляються пари з кроком 8. Це пари елементів 1-9, 2-10, 3-11,4-12, 5-13, 6-14, 7-15, 8-16. Якщо значення елементів в парі не впорядковані за збільшенням, то елементи міняються місцями. Назвемо цей етап 8-сортуванням.
Наступний етап - 4-сортування, на якому елементи у масиві діляться на четвірки: 1-5-9-13, 2-6-10-14, 3-7-11-15,4-8-12-16. Виконується сортування в кожній четвірці.
Наступний етап - 2-сортування, коли елементи у масиві діляться на 2 групи по 8: 1-3-5-7-9-11-13-15 і 2-4-6-8-10-12-14-16. Виконується сортування в кожній вісімці. Нарешті весь масив упорядковується методом вставок. Оскільки дальні елементи вже перемістилися на своє місце або знаходяться поблизу від нього, цей етап буде значний менш трудомістким, ніж при сортуванні вставками без попередніх "дальніх обмінів".
Багатофазне сортування
Ідея багатофазного сортування полягає в тому, що з наявних m допоміжних масивів (m-1) масив служить для введення зливаних послідовностей, а один - для виведення утворюваних серій. Як тільки один з масивів введення стає порожнім, його починають використовувати для виведення серій, одержуваних при злитті серій нового набору (m-1) масиві. Таким чином, є перший крок, при якому серії
початкового масиву розподіляються по m-1 допоміжному масиву, а потім виконується багатопутнє злиття серій з (m-1) масиву, поки в одному з них не утворюється одна серія.
Очевидно, що при довільному початковому розподілі серій по допоміжних масивах алгоритм може не зійтися, оскільки в єдиному непорожньому масиві існуватиме більш, ніж одна серія. Припустимо, наприклад, що використовується три масиви B1, B2 і B3, і при початковому розподілі у масив B1 поміщено 10 серій, а у масив B2 - 6. При злитті B1 і B2 до моменту, коли ми дійдемо до кінця B2, в B1 залишаться 4 серії, а в B3 потраплять 6 серій. Продовжиться злиття B1 і B3, і при завершенні перегляду B1 в B2 міститимуться 4 серії, а в B3 залишаться 2 серії. Після злиття B2 і B3 в кожному з масивів B1 і B2 міститиметься по 2 серії, які злитимуться і утворюють 2 серії в B3 при тому, що B1 і B2 - порожні. Тим самим, алгоритм не зійшовся (таблиця 3.2).
Таблиця 3.2. Приклад початкового розподілу серій, при якому трифазне зовнішнє сортування не приводить до потрібного результату
Число серій у масиві B1 Число серій у масиві B2 Число серій у масиві B3
10 6 0
4 0 6
0 4 2
2 2 0
0 0 2
Спробуємо зрозуміти, яким повинен бути початковий розподіл серій, щоб алгоритм трифазного сортування благополучно завершував роботу і виконувався максимально ефективно. Для цього розглянемо роботу алгоритму в зворотному порядку починаючи від бажаного кінцевого стану допоміжних масивів. Нас влаштовує будь-яка комбінація кінцевого числа серій у масивах B1, B2 і B3 з (1,0,0), (0,1,0) і (0,0,1). Для визначеності виберемо першу комбінацію. Для того, щоб вона склалася необхідно, щоб на безпосередньо попередньому етапі злиття існував розподіл серій (0,1,1). Щоб отримати такий розподіл, необхідно, щоб на безпосередньо попередньому етапі злиття розподіл виглядав як (1,2,0) або (1,0,2). Знову для визначеності зупинимося на першому варіанті. Щоб його отримати, на попередньому етапі годилися б наступні розподіли: (3,0,2) і (0,3,1). Але другий варіант гірше, оскільки він приводиться до злиття тільки однієї серії з файлів B2 і B3 тоді як за наявності першого варіанту розподілу злитимуться дві серії з файлів B1 і B3. Побажанням до попереднього етапу була б наявністьрозподілу (0,3,5), ще раніше - (5,0,8), ще раніше - (13,8,0) і т.д.
Цей розгляд показує, що метод трифазного зовнішнього сортування дає бажаний результат і працює максимально ефективно (на кожному етапі зливається максимальне число серій) якщо початковий розподіл серій між допоміжними файлами описується сусідніми числами Фібоначчі. Нагадаємо, що послідовність
чисел Фібоначчі починається з 0, 1, а кожне наступне число утворюється як сума двох попередніх:
(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ....)
Аналогічні (хоча і більш громіздкі) міркування показують, що в загальному вигляді при використовуванні m допоміжних файлів умовою успішного завершення і ефективної роботи методу багатофазного зовнішнього сортування є те щоб початковий розподіл серій між m-1 файлами описувався сумами сусідніх (m-1), (m-2) ..., 1 чисел Фібоначчі порядку m-2.
Послідовність чисел Фібоначчі порядку p починається з p нулів, (p+1)-й елемент рівний 1 а кожний наступний дорівнює сумі попередніх p+1 елементів. Нижче показано початок послідовності чисел Фібоначчі порядка
4:
(0, 0, 0, 0, 1, 1, 2, 4, 8, 16, 31, 61 ...)
При використовуванні шести допоміжних файлів ідеальними розподілами серій є наступні:
1 0 0 0 0
1 1 1 1
Loading...

 
 

Цікаве