оруч, як в алгоритмі простих вставок (п.1), але і далеко один від одного, що значно скорочує загальний число операцій переміщення елементів. Для прикладу візьмемо файл з 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. Виконується сортування в кожній четвірці. Сортування може виконуватися методом простих вставок (п.1). Наступний етап - 2-сортування, коли елементи в файлі діляться на 2 групи по 8:
1-3-5-7-9-11-13-15 і 2-4-6-8-10-12-14-16. Виконується сортування в кожній вісімці. Нарешті весь файл впорядковується методом простих вставок. Оскільки далекі елементи вже перемістилися на своє місце або знаходяться поблизу від нього, цей етап буде значно менш трудомістким, ніж при сортуєте вставками без попередніх "далеких" обмінів. p> Файл після остаточної сортування (1-сортування): 61 87 154 170 275 426 503 509 512 612 653 677 703 765 897 908
Час роботи алгоритму t приблизно оцінюється формулою: t = a * N ** b
де a і b - невідомі константи, залежать від програмної реалі-
ції алгоритму.
В
Вставки в зв'язаний список
Серед загальних способів поліпшення алгоритму простих вставок можна розглянути спосіб, заснований на зміні структури даних. Сортування простими вставками складається з двох основних операцій:
- перегляду вихідного файлу з порівнянням змінної Х з
елементами K [i] файлу;
- вставки нового елемента шляхом зрушення елементів, що залишилися
вправо.
Файл досі розглядався як лінійний список і для виконання операції вставки в ньому необхідно перемістити в середньому половину еле-ментів. Відомо, що для операцій вставки ідеально подходітсвязанний список, так як в цьому випадку вставка вимагає всього лише зміни декількох зв'язків. Операція послідовного перегляду для зв'язаного списку майже так само проста, як і для лінійного списку. Оскільки файл завжди проглядається в одному напрямі, то досить мати список тільки з одним зв'язком. З іншого боку пов'язане розподілення унеможливлює бінарний пошук, тому набуваючи перевагу у виконанні операції вставки, ми втрачаємо по порівняно з бінарним пошуком в ефективності операції перегляду і порівняння. Розглянемо алгоритм простих вставок на пов'язаному вперед списку. p> Дан файл у вигляді связанниого списку, кожен елемент якого містить крім ключа K [i] ще і покажчик на наступний елемент L [i].
Крім того є ще додаткова змінна L [0], містить покажчик на останній N-й елемент файлу. Покажчик L [N] дорівнює нулю, що є ознакою кінця списку елементів. p> Час роботи алгоритму t приблизно оцінюється формулою: t = a * NР… + b * N
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
Вставки в кілька пов'язаних списків
Ідея методу грунтується на припущенні, що ключі у вихідному файлі мають значення в деякому відомому діапазоні MAX і в цьому діапазоні вони розподілені досить рівномірно. Тоді за аналогією з методом вставки в один зв'язаний список можна організувати декілька, наприклад, Q списків. Величина Q залежить від очікуваного середнього количес-тва елементів M в кожному списку тобто Q = N/M, N - кількість ключів.
При розробці програми потрібно проаналізувати залежність часу роботи методу від параметра М для різних вихідних файлів і дати рекомендації з вибору оптимального значення.
Схема алгоритму має наступний вигляд. Через Q позначена кількість списків, масив B [1] ... B [Q] служить для зберігання покажчиків на початку окремих списків. Перед початком роботи алгоритму елементи масиву У передбачаються рівними 0. Кожен i-й елемент вихідного файлу містить ключ K [i] і покажчик L [i] на наступний елемент переліку. Значення L [i] = 0 відповідає останньому елементу в списку, покажчик B [1] вказує на початок першого підсписка і одночасно на початок усього списку. Через minK позначено мінімальне значення ключа у файлі, через М - середнє вибране значення кількості елементів у підсписку. d - номер поточного списку, до якого повинен бути вставлений елемент K [j]. Величина R = MAX/Q є діапазон значень ключів, який припадає на один список.
Час роботи алгоритму t приблизно оцінюється формулою: t = a * NР… + b * N
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
Обмінна сортування
Назва цієї групи методів сталося від основного типу операцій, використовуваного в алгоритмах - обмін двох елементів у файлі своїми значеннями. Ця операція використовується і в інших групах, тому класифікацію не можна визнати цілком суворої, але дане поділ проте є традиційним. Файл, що підлягає сорт...
