Алгоритми сортування

КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ

Сортуванням називають впорядковування по ключах (тобто за якою-небудь ознакою) елементів деякої структури даних на якій визначено відношення порядку.

У залежності від того, чи знаходяться елементи структур даних у внутрішній (оперативній) пам’яті або у зовнішній пам’яті (на зовнішніх пристроях),розрізняють внутрішнє та зовнішнє сортування.

Нехай існують послідовність a0, a1... an і функція порівняння, яка на будь-яких двох елементах послідовності приймає одне з трьох значень: менше, більше або дорівнює. Задача сортування полягає у перестановці елементів послідовності так, щоб виконувалася умова: ai <= ai+1, для всіх i від 0 до n.

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

Мабуть, жодна інша проблема не породила такої кількості найрізноманітніших рішень, як задача сортування. Чи існує певний "універсальний, найкращий алгоритм"? Маючи приблизні характеристики вхідних даних, можна підібрати метод, який працює оптимальним чином.

Для того, щоб обґрунтовано зробити такий вибір, розглянемо параметри, по яких проводититься оцінка алгоритмів.

1. Час сортування - основний параметр, що характеризує швидкодію алгоритму.

2. Пам’ять - ряд алгоритмів вимагає виділення додаткової пам’яті під тимчасове зберігання даних. При оцінці пам’яті, що використовується, не враховується місце, яке займає початковий масив і незалежні від вхідної послідовності витрати, наприклад, на зберігання коду програми.

3. Стійкість - стійке сортування не міняє взаємного розташування рівних елементів. Така властивість може бути дуже корисною, якщо вони складаються з декількох полів, як на рис. 5, а сортування відбувається по одному з них, наприклад, по x.

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

Ще однією важливою властивістю алгоритму є його сфера застосування. Тут основних позицій дві:

· внутрішні сортування працюють з даним в оперативній пам'яті з довільним доступом;

· зовнішні сортування упорядковують інформацію, розташовану на зовнішніх носіях.

Це накладає деякі додаткові обмеження на алгоритм: доступ до носія здійснюється послідовним чином: в кожний момент часу можна зчитати або записати тільки елемент, наступний за слідуючим; o об’єм даних не дозволяє їм розміститися в ОЗП; Крім того, доступ до даних на носію здійснюється набагато повільніше, ніж операції з оперативною пам’яттю.

Даний клас алгоритмів ділиться на два основні підкласи:

· Внутрішнє сортування оперує з масивами, що цілком поміщаються в оперативній пам’яті з довільним доступом до будь-якої комірки. Дані звичайно сортуються на тому ж місці, без додаткових витрат.

· Зовнішнє сортування оперує з пристроями великого об'єму, що запам’ятовують, але з доступом не довільним, а послідовним (сортування файлів), тобто у даний момент ми “бачимо” тільки один елемент, а витрати на перемотування у порівнянні з пам’яттю невиправдано великі. Це приводить до спеціальних методів сортування, які звичайно використовують додатковий дисковий простір.

1. Функція складності алгоритму

Для вирішення багатьох проблем існує безліч різних алгоритмів. Який з них вибрати для вирішення конкретного завдання? Це питання дуже ретельно опрацьовується в програмуванні. Ефективність програми є дуже важливою її характеристикою. Ефективність програми має дві складові: пам'ять (або простір) і час. Просторова ефективність вимірюється кількістю пам'яті, потрібної для виконання програми. Комп'ютери володіють обмеженим об'ємом пам'яті. Якщо дві програми реалізують ідентичні функції, то та, яка використовує менший об'єм пам'яті, характеризується більшою просторовою ефективністю. Інколи пам'ять стає домінуючим чинником в оцінці ефективності програм. Проте останніми роками у зв'язку з швидким її здешевленням ця складова ефективності поступово втрачає своє значення. Тимчасова ефективність програми визначається часом, необхідним для її виконання. Кращий спосіб порівняння ефективність алгоритмів полягає в зіставленні їх порядків складності. Цей метод застосовний як до тимчасової, так і просторовій складності. Порядок складності алгоритму виражає його ефективність зазвичай через кількість оброблюваних даних. Наприклад, деякий алгоритм може істотно залежати від розміру оброблюваного масиву. Якщо, скажімо, час обробки подвоюється з подвоєнням розміру масиву, то порядок тимчасової складності алгоритму визначається як розмір масиву. Порядок алгоритму — це функція, домінуюча над точним вираженням тимчасовій складності. Функція f(n) має порядок 0(g(n)), якщо є константа К і лічильник n0 такі, що f(n)(K*g(n)) для п > n0. Наприклад: відомо, що точний час обробки масиву визначається з рівняння:

1.1. Види функції складності алгоритмів

Для оцінки ефективності алгоритмів використовується функція складності алгоритму, яка позначається прописною буквою О, в круглих дужках записується аргумент. Наприклад, функція складності 0(n^2) читається як функція складності по-рядка п^2. функція складності алгоритму — це функція, що визначає кількість порівнянь, перестановок, а також тимчасові і ресурсні витрати на реалізацію алгоритму.

Функція складності приймає наступний ряд значень (мал. 2.15).

Чим правіше на осі розташована функція складності, тим менш ефективний алгоритм.

· Методи проста вставка, простий і стандартний обмін мають функцію складності О(п^2).

· Метод Хоара і пірамідальне сортування мають функцію складності 0(n log2n)

· Метод Шелла і турнірне сортування мають функцію складності 0(0,3n(1оg2n)^2).

1.2. Cкладність алгоритмів сортування

Дата добавления: 2013-12-14