НОУ ІНТУІТ, Лекція, Швидке сортування
Розбиття по медіані з трьох
Іншим удосконаленням швидкого сортування є використання центрального елемента, який з більшою ймовірністю поділяє файл близько до середини. Є кілька можливостей зробити це. Досить надійний спосіб уникнути гіршого випадку полягає у використанні випадкового елемента масиву як центральний. Тоді ймовірність найгіршого вибору дуже мала. Цей метод є простим прикладом імовірнісного алгоритму (probabilistic algorithm) - алгоритму, який використовує випадковий вибір для досягнення хорошої продуктивності з високою ймовірністю, незалежно від впорядкованості вхідних даних. Далі в цій книзі ми побачимо численні приклади використання випадкового вибору розробки алгоритмів, особливо якщо можлива регулярність вхідних даних. На практиці використання генератора випадкових чисел для швидкого сортування може виявитися зайвим: досить ефективний довільний вибір.
Інший поширений спосіб визначення кращого центрального елемента полягає у вибірці трьох елементів з файлу та використанні як центральний елемент їх медіани. Якщо вибрати за ці три елементи лівий, правий та середній елементи масиву, то заразом можна включити в схему та сигнальні елементи: сортуємо три обрані елементи (використовуючи метод трьох обмінів, описаний в "Елементарні методи сортування"), потім обмінюємо середній з них з елементом a[r-1] , а потім виконуємо алгоритм розбиття для a[l+1], . a[r-2]. Це удосконалення називається методом медіани із трьох (median-of-three).
Метод медіани із трьох підвищує ефективність сортування трьома способами. По-перше, він суттєво знижує ймовірність появи найгіршого випадку при сортуваннібудь-якого реального файлу. Щоб сортування виконалося за час порядку N 2 , два з трьох вибраних елементів повинні бути найбільшими або найменшими елементами файлу, і ця подія повинна постійно повторюватися для більшості розбиття. По-друге, він усуває необхідність сигнальному елементі, т.к. цю функцію перебирає одне із трьох елементів, перевірених перед розбиттям. По-третє, він зменшує загальний середній час виконання алгоритму приблизно 5%.
Поєднання методу медіани із трьох із відсіканням невеликих підфайлів може покращити час виконання швидкого сортування порівняно з елементарною рекурсивною реалізацією на 20-25%. Програма 7.4 є реалізацією, що увібрала у собі всі ці удосконалення.
Можна було б продовжити вдосконалення програми, видаливши рекурсію, замінивши виклики підпрограм безпосередньою вставкою їхнього коду, використовуючи сигнальні значення тощо. Однак у сучасних машинах такі виклики процедур є цілком ефективними, і вони знаходяться поза внутрішнім циклом. Більш важливим є те, що застосування відсікання невеликих підфайлів компенсує можливі додаткові витрати (поза внутрішнім циклом). Основною причиною використання нерекурсивної реалізації з явним стеком є гарантоване обмеження розміру стеку (див. рис. 7.10).
Сортування спочатку меншого підфайлу гарантує, що навіть у гіршому випадку розмір стека логарифмічно залежатиме від розміру файлу. Тут наведено графіки розмірів стека тих самих файлів, як і рис. 7.5, але при сортуванні спочатку меншого підфайлу (ліворуч) та з додаванням модифікації медіани з трьох (праворуч). Ці діаграми ніяк не пов'язані з часом виконання, який залежить швидше від обсягу файлів у стеку, ніж від кількості. Наприклад, для третього (часткововпорядкованого) файлу не потрібний великий стек, проте сортування виконується повільно, т.к. оброблювані підфайли зазвичай мають великий розмір.
Можливі й подальші покращення алгоритму (наприклад, можна використовувати медіану з п'яти або більше елементів), але для випадково впорядкованих файлів заощаджений час буде незначним. Можна отримати значну економію часу, переписавши внутрішні цикли (чи всю програму) на асемблері чи машинних кодах. Ці пропозиції були багато разів перевірені фахівцями у солідних додатках, які використовують сортування (див. розділ посилань).
Програма 7.4. Удосконалене швидке сортування
Вибір медіани з першого, середнього та останнього елементів як центральний елемент та відсікання рекурсії для невеликих підфайлів може значно підвищити продуктивність швидкого сортування. Дана реалізація здійснює розбиття по медіані з першого, середнього та останнього елементів масиву (і інакше не включає їх у процес розбиття). Файли довжиною 11 і менше ігноруються під час розбиття, а потім для завершення сортування використовується метод insertion з "Елементарні методи сортування".
Для випадково впорядкованих файлів перша перестановка у програмі 7.4 не потрібна. Вона залишена тому, що призводить до оптимального розбиття вже впорядкованих файлів, а також тому, що є захистом від позаштатних ситуацій, які можуть зустрітися на практиці (див., наприклад, вправа 7.33). На рис. 7.11 ілюструється ефективність використання середнього елемента щодо місця розбиття для файлів з різним початковим розподілом ключів.
Варіант вибору медіани із трьох (особливо при виборі середнього елемента файлу) значно підвищує стійкість процесу розбиття.Вироджені види файлів, показані на рис. 7.4 обробляються дуже добре. Інший варіант, що досягає тієї ж мети - використання випадкового центрального елемента.
Метод медіани з трьох є спеціальним випадком загального принципу: можна випадковим чином вибрати записи з невідомого файлу і використовувати властивості цієї вибірки для оцінки властивостей всього файлу. У разі швидкого сортування для отримання збалансованого розбиття слід оцінити медіану випадкової вибірки. Алгоритм такий, що нам не потрібна дуже точна оцінка (або оцінка взагалі не потрібна, якщо вона потребує великих обчислювальних витрат); ми хочемо уникнути дуже невдалої оцінки. Якщо для оцінки використовується випадкова вибірка лише з одного елемента, виходить алгоритм ймовірності, який майже напевно виконується швидко, незалежно від вхідних даних. Якщо випадково вибрати з файлу три або п'ять елементів, а потім використовувати для розбиття їх медіану, вийде краще розбиття, але це вдосконалення буде досягнуто ціною виконання та оцінки вибірки.
На великих випадково впорядкованих файлах швидке сортування (програма 7.1) працює майже втричі швидше за сортування Шелла (програма 6.6). Відсікання невеликих підфайлів та розбиття по медіані з трьох (програма 7.4) ще більше скорочують час сортування.
| 12500 | 6 | 2 | 2 | 2 | 3 | 2 | 3 |
| 25000 | 10 | 5 | 5 | 5 | 5 | 4 | 6 |
| 50000 | 26 | 11 | 10 | 10 | 12 | 9 | 14 |
| 100000 | 58 | 24 | 22 | 22 | 25 | 20 | 28 |
| 200000 | 126 | 53 | 48 | 50 | 52 | 44 | 54 |
| 400000 | 278 | 116 | 105 | 110 | 114 | 97 | 118 |
| 800000 | 616 | 255 | 231 | 241 | 252 | 213 | 258 |
7.28. У реалізації методу медіани з трьох елементів, що становлять випадкову вибірку, не беруть участь у процесі розбиття. Одна з причин - вони можуть бути використані як сигнальні ключі. Наведіть ще одну причину.
7.29. Реалізуйте швидке сортування, засноване на розбиття за медіаною випадкової вибірки з п'яти елементів файлу. Елементи вибірки не повинні брати участь у розбиття (див. вправу 7.28). Порівняйте продуктивність отриманого алгоритму з методом медіани з трьох великих випадково впорядкованих файлів.
7.30. Виконайте програму з вправи 7.29 для великих файлів із спеціальною організацією - наприклад, для відсортованих файлів, файлів у зворотному порядку або файлів з однаковими ключами. Як відрізняється її продуктивність для цих файлів від продуктивності випадково впорядкованих файлів?
7.31. Реалізуйте швидке сортування за допомогою випадкової вибірки з 2 k - 1
елементів. Спочатку відсортуйте вибірку, потім рекурсивною програмою розбийте файл по медіані вибірки, а половину вибірки, що залишилися, помістіть в кожен підфайл так, щоб вони використовувалися в цих підфайлах без подальшого сортування. Такий методСортування називається сортуванням методом випадкової вибірки (samplesort).
7.32. Визначте емпіричним шляхом найкращий розмір вибірки для сортування
методом випадкової вибірки (див. вправу 7.31) для N = 10 3 , 10 4 , 10 5 та 10 6 . Чи має значення, який вид сортування використовується для впорядкування самої вибірки: швидке сортування чи сортування методом випадкової вибірки?
7.33. Покажіть, що якщо у програмі 7.4 прибрати першу перестановку та пропускати ключі, рівні центральному, то час її виконання для упорядкованих назад файлів буде квадратичним.