уванню, в загальному випадку складається з елементів-записів, що включають інформаційну частина і ключі, за якими проводиться впорядкування по зростанню.
Оскільки інформаційна частина майже не впливає на процес сортування, будемо припускати, що файли, використовувані в прикладах, состот тільки з елементів-ключів, а інформаційна частину запису відсутня.
Метод бульбашки
Алгоритм досить очевидний.
Пари стоять поруч елементів проглядаються в напрямку знизу вгору і порівнюються. Якщо верхній елемент виявляється менше нижнього, то вони міняються місцями. Продовжуючи цей процес циклічно, ми врешті-решт прийдемо до відсортованих файлу.Файл розташований вертикально знизу вгору, щоб ефект спливаючого бульбашки виглядав більш наочно. Елементи з великим значенням ключа "Спливають" вгору, після послідовних сравнівненій з сусідніми елементами.
Час роботи алгоритму t приблизно оцінюється формулою: t = a * NР… + b * N
де a, b - невідомі константи, що залежать від програмної реалі-
ції алгоритму.
Модифікація методу бульбашки
Модифікація методу бульбашки складається в тому, що файл можна переглядати як з початку до кінця, так і з кінця до початку поперемінно. Це трохи скорочує число переміщень елементів.
Час роботи алгоритму t приблизно оцінюється формулою: t = a * NР… + b * N
де a, b - невідомі константи, залежать від програмної реалізації алгоритму.
В
Швидке сортування.
Основна стратегія прискорення алгоритмів сортування - обміни між якомога більш далекими елементами вихідного файлу - в методі швидкого сортування реалізована за рахунок того, що один з ключів у вихідному файлі використовується для розділення його на два подфайла так, щоб зліва від обраного елемента знаходилися тільки елементи з меншими ключами, а праворуч - тільки з великими. Елемент, розділяє файл, поміщається між його двома подфайламі і процедура виконується рекурсивно для кожної половини до тих пір, поки в черговому новому подфайле НЕ виявиться менше, ніж М елементів, де М - заздалегідь вибране число.
Сортування подфайлов, що містять менше ніж М елементів, виконується яких-небудь простим методом, наприклад простими вставками. Таким чином, реалізація методу залежить від двох параметрів: значення М і способу вибору елемента, який призначений для поділу файлу на дві частини.
Блок вибору Х в простому випадку формулюється як X = K [l], проте це може призвести до вкрай неефективного алгоритмом. Найбільш просте краще рішення - вибирати Х як випадковий ключ з діапазону K [l] ... K [r] і обміняти його з K [l]. p align=left> Час роботи алгоритму t приблизно оцінюється формулою:
t = a * N * logN + b * N
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
Обмінна поразрядное сортування
Даний метод використовує двійкове подання ключів. Файл сортується послідовно по бітам двійкового подання ключів, починаючи зі старшого. Ключі, що мають значення даного біта, равноенулю, ставляться в ліву половину файлу, а ключі зі значенням біта 1 в праву. Функція b (ключ) повертає значення ьіта з номером b аргументу, m-максимальна кількість значущих бітів в ключах.
Час роботи алгоритму t приблизно оцінюється формулою: t = a * N * logN + b * N
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
Паралельна сортування Бетчера
Для отримання алгоритму обмінного сортування, час роботи якого менше, ніж NР…, необхідно вибирати для порівняння і обміну ключі, розташовані можливо далі один від одного. Ця ідея вже була реалізована в алгоритмі сортування Шелла вставок з убутним кроком, проте в даному алгоритмі порівняння виконуються по-іншому.
Час роботи алгоритму t приблизно оцінюється формулою: t = a * N * (logN) Р…
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
Сортування за допомогою вибору
Ідея методу досить проста: знайти найбільший елемент файлу і по-ставити його на місце N, знайти наступний максимум і поставити його на місце N-1 і т.д. до 2-го елемента. p> Час роботи алгоритму t приблизно оцінюється формулою: t = a * NР… + b * N * logN
де a, b - невідомі константи, що залежать від програмної реалізації алгоритму.
Використання пов'язаного списку для зберігання інформації про проміжні максимумах.
В алгоритмі максимум серед K [1] ... K [j-1] визначається в циклі від j-1 до 1 c метою забезпечити менше число обмінів у випадку рівності ключів і збереженні колишнього порядку рівних елементів. Однак, якщо змінити порядок перегляду елементів на протилежний і змінити структуру даних, ввівши додаткові покажчики, можна приклад-але в два рази скоротити число повторень у циклі пошуку максісмума. Кожен ключ K [i] постачається покажчиком L [i] на елемент, мак...
