Поліпшені алгоритми сортування
Усі алгоритми, розглянуті в попередніх розділах, мають один фатальний недолік - час виконання має порядок n 2 . Це робить сортування великих обсягів даних дуже повільним. Фактично, у якийсь момент ці алгоритми стають надто повільними, щоб їх застосовувати [1] . На жаль, страшні історії про "сортування, що тривали три дні", часто реальні. Коли сортування займає занадто багато часу, причиною цього є неефективність використаного в ньому алгоритму. Тим не менш, першою реакцією в такій ситуації часто стає оптимізація коду вручну, можливо шляхом переписування його на асемблері. Незважаючи на те, що ручна оптимізація іноді прискорює процедуру на постійний множник [2] якщо алгоритм сортування не ефективний, сортування завжди буде повільним незалежно від того, наскільки оптимально написаний код. Слід пам'ятати, якщо час роботи процедури пропорційно n 2 то збільшення швидкості коду або комп'ютера дасть лише невелике поліпшення [3] , оскільки час виконання збільшується як n 2 . (Насправді, крива n 2 на рис. 21.1 (бульбашкове сортування) розтягнута вправо, але в іншому відповідає дійсності.) Існує правило: якщо алгоритм, що використовується в програмі, занадто повільний сам по собі, ніякий обсяг ручної оптимізації не зробить програму досить швидкою. Рішення полягає у застосуванні кращого алгоритму сортування.
Нижче описані два чудові методи сортування. Перший називається сортуванням Шелла. Друге — швидке сортування — зазвичай вважається найкращим алгоритмом сортування. Обидва методи є більш досконалими способами сортування та мають набагато кращу загальну продуктивність, ніж будь-який із наведених вище простих методів.
Сортування Шелла
Мал. 21.2. Сортування Шелла
Те, що цей метод дає хороші результати, або навіть те, що він взагалі сортує масив, побачити не так просто. Тим не менш, це правильно. Кожен прохід сортування поширюється відносно невелика кількість елементів або на елементи, розташовані вже у відносному порядку. Тому сортування Шелла ефективне, а кожен прохід підвищує впорядкованість [6] .
Конкретна послідовність кроків може бути інший. Єдине правило полягає в тому, щоб останній крок дорівнював 1. Наприклад, така послідовність:
дає хороші результати та застосовується у показаній тут реалізації сортування Шелла. Слід уникати послідовностей, які є ступенями числа 2 - з математично складних міркувань вони зменшують ефективність сортування (але сортування, як і раніше, працює!).
Ви могли помітити, що внутрішній цикл for має дві умови перевірки. Очевидно, що порівняння x необхідне процесу сортування. Вираз j>=0 запобігає виходу за кордон масиву items . Ці додаткові перевірки до певної міри знижують продуктивність сортування Шелла.
У трохи модифікованих версіях даного методу сортування застосовуються спеціальні елементи масиву, звані сигнальними мітками . Вони не належать до власне сортованого масиву, а містять спеціальні значення, що відповідають найменшому можливому та найбільшому можливому елементам [7] . Це усуває необхідність перевірки виходу за межі масиву. Однак застосування сигнальних міток елементів вимагає конкретної інформації про дані, що сортуються, що зменшує універсальність функції сортування.
Аналіз сортування Шелла пов'язаний з дуже складними математичними завданнями, які виходять далеко за межіцієї книги. Візьміть на віру, що час сортування пропорційно
при сортуванні n елементів [8]. А це вже суттєве покращення порівняно із сортуваннями порядку n 2 . Щоб зрозуміти, наскільки воно велике, зверніться до рис. 21.3, на якому показані графіки функцій n 2 та n 1,2 . Тим не менш, не варто надмірно захоплюватися сортуванням Шелла - швидке сортування ще краще.
Мал. 21.3. Спроба наочного уявлення кривих n 2 і n 1,2. Хоча викреслити ці криві з точним дотриманням масштабу на якомусь значимому для цілей сортування інтервалі зміни кількості записів (n), наприклад, на інтервалі від 0 до 1000, неможливо, отримати уявлення про поведінку цих кривих можна за допомогою графіків функцій у= (n/100) 2 і у = (n/100) 1,2 . Для порівняння побудований також графік прямої у = n/100. Крім того, щоб отримати уявлення про зростання цих кривих, можна на осі ординат набути логарифмічного масштабу — це все одно, що накреслити логарифми цих функцій.
Швидке соритування
Швидке сортування, придумане Ч. А. Р. Хоаром [9] (Charles Antony Richard Hoare) і назване його ім'ям, є найкращим методом сортування з представлених у цій книзі і зазвичай вважається найкращим з існуючих в даний час алгоритмом сортування загального призначення. В її основі лежить сортування обмінами - дивовижний факт, враховуючи жахливу продуктивність бульбашкового сортування!
Швидке сортування побудовано ідеї поділу. Загальна процедура полягає в тому, щоб вибрати деяке значення, яке називається компарандом (comparand) [10] , а потім розбити масив на дві частини. Усі елементи, великі або рівні компаранду, переміщаються однією сторону, а менші — в іншу. Потім цей процес повторюється длякожної частини до тих пір, поки масив не буде відсортовано. Наприклад, якщо вихідний масив складається із символів fedacb , а як компаранд використовується символ d , перший прохід швидкого сортування переупорядкує масив наступним чином:
Потім сортування повторюється обох половин масиву, тобто bса і def . Як ви бачите, цей процес за своєю суттю є рекурсивним, і, дійсно, в чистому вигляді швидке сортування реалізується як рекурсивна функція [11] .
Значення компаранда можна вибирати двома способами - випадковим чином або усереднивши невелику кількість значень масиву. Для оптимального сортування необхідно вибирати значення, яке розташоване в середині діапазону всіх значень. Проте більшість наборів даних це зробити непросто. У найгіршому разі обране значення виявляється однією з крайніх. Тим не менш, навіть у цьому випадку швидке сортування працює правильно. У наведеній нижче версії швидкого сортування як компаран вибирається середній елемент масиву.
У цій версії функція quick() готує виклик головної функції qs() . Це забезпечує загальний інтерфейс з параметрами items і count, але несуттєво, оскільки можна викликати безпосередньо функцію qs() з трьома аргументами.
Отримання кількості порівнянь та обмінів, які виконуються при швидкому сортуванні, потребує математичних викладок, що виходять за межі цієї книги. Тим не менш, середня кількість порівнянь дорівнює
а середня кількість обмінів приблизно дорівнює
Ці величини набагато менші за відповідні характеристики розглянутих раніше алгоритмів сортування.
Необхідно згадати про один особливо проблематичний аспект швидкого сортування. Якщо значення компаранду в кожному розподілі дорівнює найбільшомузначенню, швидке сортування стає "повільним сортуванням" з часом виконання порядку n 2 . Тому уважно вибирайте метод визначення компаранда. Цей метод часто визначається природою даних, що сортуються. Наприклад, у дуже великих списках поштової розсилки, в яких сортування відбувається за поштовим індексом, вибір простий, тому що поштові індекси досить рівномірно розподілені - компаранд можна визначити за допомогою простої функції алгебри. Однак в інших базах даних найчастіше найкращим вибором є випадкове значення. Популярний і досить ефективний метод — вибрати три елементи з частини масиву, що сортується, і взяти в якості компаранда значення, розташоване між двома іншими.
[1] Звичайно, це не означає, що функція f (n) = n 2 в якійсь точці зростає стрибкоподібно. Зовсім ні! Просто при збільшенні розміру масиву n змінюється характер сортування, з внутрішньої вона фактично стає зовнішньою, коли масив не міститься в оперативній пам'яті і починається інтенсивне підкачування сторінок, а за нею пробуксовування механізму віртуальної пам'яті. Ось ці події дійсно можуть наступити раптово, і тоді може здатися, що незначне збільшення масиву, що сортується, або просто додавання якого-небудь зовсім незначного завдання призведе до катастрофічного збільшення часу сортування (наприклад в десятки разів!).
[3] Дійсно, щоб збільшити в m разів розмір сортованого масиву за збереження часу сортування, швидкодія процесора доведеться збільшити в m 2 разів за умови, що час доступу до елементів масиву не збільшиться, тобто. не зменшиться, наприклад, ефективність підкачування сторінок.
[5] Крок - відстань між елементами, що сортуються на конкретному етапі сортування.
[6] Тобто.зменшує кількість заворушень (інверсій).
[8] Взагалі, час сортування Шелла залежить від послідовності кроків. (Втім, мінімум дорівнює, звичайно, n log 2 n.) Оптимальна послідовність не відома досі. Дональд Кнут досліджував різні послідовності (не забувши і послідовність Фібоначчі). Фактично він дійшов висновку, що у визначенні найкращої послідовності є якесь "чаклунство". У 1969 р. Воган Пратт виявив, що й усі кроки вибираються з безлічі чисел виду 2 p 3 q , менших n, час роботи буде порядку n(log n) 2 . А.А. Папернов та Г.В. Стасевич 1965 р. довели, що максимальний час сортування Шелла вбирається у О(n 1,5 ), причому зменшити показник 1,5 не можна. Велике число експериментів із сортуванням Шелла провели Джеймс Петерсон і Девід Л. Рассел у Стенфордському університеті в 1971 р. Вони намагалися визначити середню кількість переміщень при 100 n 250 000 для послідовності кроків 2 k -1. Найбільш підходящими формулами виявилися 1,21 n 1,26 і ,39 n (ln n )-2,33 n ln n . Але при зміні діапазону n виявилося, що коефіцієнти у поданні статечною функцією практично не змінюються, а коефіцієнти у логарифмічному поданні змінюються досить різко. Тому природно припустити, що саме статечна функція описує справжню асимптотичну поведінку сортування Шелла.
[9] Зустрічається також написання Ч. Е. Р. Хоор.
[10] Компаранд - операнд в операції порівняння. Іноді називається також основою та критерієм розбиття.
[11] Якщо хочете уникнути рекурсії, не хвилюйтеся, все дуже легко переписується навіть для Фортрана IV, у згаданій раніше літературі ви легко знайдете потрібний нерекурсивний варіант.