НОУ ІНТУІТ, Лекція, Порозрядне сортування
Бінарне швидке сортування
Припустимо, що ми можемо переупорядкувати записи у файлі таким чином, що всі ключі, що починаються з біта 0, будуть розташовані перед ключами, що починаються з біта 1. Тоді можна скористатися рекурсивним методом сортування, який є одним із варіантів швидкого сортування (див. "Швидка" сортування" ): розбиваємо файл цим способом і потім незалежно сортуємо обидва підфайли. Для переупорядкування файлу ми переглядаємо його зліва до виявлення ключа, який починається з біта 1, потім переглядаємо праворуч до виявлення ключа, який починається з біта 0, обмінюємо їх і продовжуємо цей процес до перехрещування покажчиків. У літературі (включаючи і більш ранні видання цієї книги) цей метод часто називають порозрядним обмінним сортуванням, а тут ми називатимемо його бінарним швидким сортуванням (binary quicksort), щоб підкреслити, що це лише простий варіант алгоритму, винайденого Хоаром, хоча він був відкритий раніше швидкого сортування (див. розділ посилань).
У програмі 10.1 представлено повну реалізацію цього методу. Застосовуваний у ній процес розбиття по суті той самий, що і в програмі 7.2, тільки як центральний елемент використовується число 2 b , а не деякий ключ з файлу. Оскільки у файлі може і не бути числа 2b, то немає і гарантії того, що в процесі розбиття хоча б один елемент потрапить до своєї остаточної позиції. Цей алгоритм відрізняється і від звичайного швидкого сортування, оскільки рекурсивні виклики виконуються для ключів розміром на 1 біт менше. Ця різниця суттєво впливає на ефективність алгоритму. Наприклад, якщо трапиться вироджене розбиття файлу з елементів N, то буде виконано рекурсивний виклик для підфайлу розміром N, але для ключів довжиноюна 1 розряд менше. Тому кількість таких дзвінків обмежена кількістю розрядів у ключі. А послідовне використання центральних елементів, які відсутні у файлі, може ввести звичайне швидке сортування в нескінченний цикл рекурсивний.
Програма 10.1. Бінарне швидке сортування
Ця програма розбиває файл за провідними бітами ключів і потім рекурсивно сортує отримані підфайли. Змінна d містить позицію аналізованого біта, починаючи з 0 (найлівішого). Розбиття завершується при j, рівному i, після чого у всіх елементів праворуч від a[i] у d -ій позиції знаходиться 1, а у всіх елементів зліва від a[i] у d -ій позиції знаходиться 0. Сам елемент a[i ] містить в d-ой позиції 1, крім того випадку, коли всі ключі файлу містять в d-ой позиції нулі. На цей випадок одразу після циклу розбиття вставлено додаткову перевірку.
Як і у випадку стандартного швидкого сортування, можливі різні варіанти реалізації внутрішнього циклу. У програмі 10.1 перевірка, чи не перетнулися значення індексів, включена в обидва внутрішні цикли. Така перевірка призводить до зайвого обміну у разі, коли i = j; цього можна уникнути за допомогою оператора break, як зроблено у програмі 7.2, хоча там обмін елемента a[i] сам із собою цілком нешкідливий. Інший спосіб - використовувати сигнальний ключ.
На рис. 10.2 показано виконання програми 10.1 на невеликому файлі, який можна порівняти з рис. 7.1 для швидкого сортування. Цей малюнок показує, як переміщуються дані, але пояснює, чому виробляються ті чи інші переміщення — залежить від двійкового представлення ключів. Більш детальне уявлення цього прикладу дано на рис. 10.3. Тут вважається, що букви закодовані простим 5-розрядним кодом, в якому i-я буква алфавіту представлена двійковимподанням числа i. Таке кодування є спрощеною версією справжніх символьних кодувань, в яких для представлення більшої кількості символів (літери верхнього та нижнього регістрів, цифри та спеціальні символи) використовується більша кількість бітів (7, 8 або навіть 16).
Розбиття по старшому розряду ще гарантує те, що хоча одне значення займе своє остаточне місце; воно лише забезпечує, що це ключі з 0 у старшому розряді передують ключам з 1 у старшому розряді. Можна порівняти цю діаграму із рис. 7.1 для швидкого сортування, хоча принцип розбиття абсолютно незрозумілий, якщо ключі не представлені у двійковому вигляді. На рис. 10.3 рис. 10.3 наведено всі деталі, які прояснюють, за якими позиціями відбувається розбиття.
Для ключів як повних слів, які з випадкових бітів, програма 10.1 повинна розпочинати роботу з самого лівого біта слова, тобто. нульового. У випадку початковий біт безпосередньо залежить від докладання, від кількості бітів у машинному слові і зажадав від внутрішнього уявлення цілих (зокрема негативних) чисел. Для однолітерних 5-розрядних ключів із рис. 10.2 та рис. 10.3 на 32-бітовій машині початковим має бути біт 27.
Цей приклад показує потенційну проблему, яка може виникнути при використанні бінарного швидкого сортування в реальних ситуаціях: досить часто можуть зустрічатися вироджені розбиття (коли всі ключі мають те саме значення розряду, за яким проводиться розбиття). Сортування невеликих чисел (у яких багато нульових старших розрядів), як у наведених нами прикладах, перестав бути чимось незвичайним. Ця ж проблема виникає і для символьних ключів: припустимо, ми будуємо 32-розрядні ключі, поєднуючи чотири символи, кожен з яких представлений устандартного 8-бітового кодування. Тоді ймовірно поява вироджених розбиття в початковій позиції кожного символу, оскільки, наприклад, всі літери нижнього регістру починаються з тих самих бітів. З цією проблемою часто доводиться стикатися під час сортування кодованих даних; аналогічні проблеми виникають і в інших видах порозрядного сортування.
Ця діаграма побудована виходячи з рис. 10.2, тільки тут значення ключів наведено у двійковому поданні, а таблиця стиснута так, щоб показати сортування незалежних підфайлів, начебто вони виконуються паралельно, і для зручності транспонована. На першому етапі файл розбивається на підфайл, всі ключі якого починаються з 0, і підфайл, всі ключі якого починаються з 1. Потім перший підфайл розбивається на підфайл, всі ключі якого починаються з 00 і підфайл, всі ключі якого починаються з 01 ; незалежно від цього в довільний момент часу другий підфайл розбивається на підфайл, всі ключі якого починаються з 10 і підфайл, всі ключі якого починаються з 11 . Цей процес припиняється при вичерпанні розрядів (для ключів, що повторюються в даному прикладі) або коли розмір підфайлів стане рівним 1.
Після того як ключ можна відрізнити за його лівими розрядами від решти, ніякі інші розряди більше не аналізуються. Ця властивість в одних ситуаціях є гідністю, в інших недоліком. Якщо ключі є справді випадкові сукупності бітів, то кожному ключі аналізуються лише lg N бітів, що зазвичай набагато менше числа бітів у ключах. Цей факт розглядається у розділі 10.6, а також у вправі 10.5 та на рис. 10.1. Наприклад, сортування файлу з 1000 записів з випадковими ключами може вимагати аналізу лише 10 або 11 бітів кожногоключа (навіть якщо ключі, скажімо, 64-розрядні). А ось для однакових ключів перевіряються усі біти. Порозрядне сортування не здатне добре працювати на файлах з великою кількістю довгих ключів, що повторюються. Бінарне швидке сортування та стандартний метод працюють досить швидко, якщо сортовані ключі складаються з абсолютно випадкових бітів (відмінність між ними полягає в основному в різниці витрат на операції вилучення бітів та порівняння), але стандартний алгоритм швидкого сортування легше пристосувати до обробки невипадкових послідовностей ключів, а тришляхове швидке сортування ідеально підходить для випадків з переважанням ключів, що повторюються.
Як і у разі швидкого сортування, структуру розбиття зручно описувати у вигляді бінарного дерева (як на рис. 10.4): корінь дерева відповідає файлу, що сортується, а два його піддерева — підфайлам після розбиття. У випадку стандартного швидкого сортування відомо, що принаймні один із записів при розбитті потрапляє у свою остаточну позицію, тому цей ключ поміщається в кореневий вузол.
Це дерево описує структуру розбиття для бінарного швидкого сортування, що відповідає рису. 10.2 та 10.3. Оскільки елементи не обов'язково займають остаточні позиції, ключі відповідають зовнішнім вузлам дерева. Така структура має таку властивість: якщо на шляху від кореня до будь-якого ключа позначити розгалуження вліво за 0, а вправо - за 1, то отримаємо значення старших розрядів цього ключа. Саме ці значення і відрізняють під час сортування цей ключ від решти. Чорні квадратики означають порожні частини розбиття (коли всі ключі переходять в іншу частину, оскільки їх значення старших розрядів збігаються). У цьому прикладі це відбувається тільки на нижніх рівнях дерева, але в принципіможливо й вище: наприклад, якби серед ключів був I чи X, їх вузли малюнку було б замінено порожнім вузлом. Зверніть увагу, що ключі, що повторюються (A і E) не можуть бути розділені (сортування помістить їх в один підфайл тільки після вичерпання всіх їх бітів).
У разі бінарного швидкого сортування відомо, що ключі потрапляють у свої остаточні позиції лише тоді, коли розмір підфайлів дійшов до 1 або коли вичерпані всі розряди ключа; так що ці ключі розміщуються на нижньому рівні дерева. Така структура називається бінарним trie-деревом (binary trie); її властивості будуть детально розглянуті в "Порозрядний пошук". Наприклад, одна з важливих і цікавих властивостей полягає в тому, що структура trie-дерева повністю визначається значеннями ключів, а не порядком їхнього прямування.
Розбиття на частини при бінарному швидкому сортуванні менш чутливі до впорядкованості ключів, ніж у стандартному швидкому сортуванні. Тут показаний процес упорядкування двох різних випадково впорядкованих файлів із 8-розрядними ключами; профілі їх розбиття практично збігаються.
Розділи розбиття в швидкому сортуванні залежать від двійкового представлення діапазону ключів і кількості елементів, що сортуються. Наприклад, якщо файли являють собою випадкові перестановки цілих чисел, менших 171 = 101010112, то розбиття по першому біту еквівалентне розбиття за значенням 128, і підфайли виходять різновеликими (розмір одного - 128, а іншого - 43). Ключі на рис. 10.5 є випадковими 8-розрядними значеннями, тому такий ефект не спостерігається, але знати про нього треба, щоб не було неприємних сюрпризів при зіткненні з ним на практиці.
Базова рекурсивна реалізація може бути вдосконалена за допомогою відмови від рекурсії та особливоїобробки невеликих підфайлів, як це було зроблено для стандартного швидкого сортування в "Швидке сортування" .
10.8. Накресліть у стилі рис. 10.2, trie-дерево, що відповідає процесу розбиття при порозрядному швидкому сортуванні ключів E A S Y Q U E S T I O N .
10.9. Порівняйте кількість обмінів, що використовуються бінарним швидким сортуванням, з кількістю обмінів, що використовуються звичайним швидким сортуванням, для 3-розрядних двійкових чисел 001, 011, 101, 110, 000, 001, 010, 111, 110, 010 .
о 10.10. Чому сортування меншого з двох під-файлів першим менш важливе у бінарному швидкому сортуванні, ніж у звичайному швидкому сортуванні?
о 10.11. Опишіть, що відбувається на другому рівні розбиття (коли розбивається лівий підфайл і коли розбивається правий підфайл) при використанні швидкого бінарного сортування для впорядкування випадкових перестановок невід'ємних цілих чисел, менших 171.
10.12. Напишіть програму, яка за один попередній прохід визначає кількість старших розрядів, однакових у всіх ключів, а потім викликає швидке бінарне сортування, модифіковане так, що вона ігнорує ці розряди. Порівняйте час виконання цієї програми з часом виконання стандартної реалізації для N = 10 3 , 10 4 , 10 5 і 10 6 якщо вхідними даними є 32-розрядні слова наступного формату: крайні праві 16 бітів — рівномірно розподілені випадкові значення, а крайні ліві 16 бітів дорівнюють 0, крім одиниці в i-ої позиції, якщо в правій половині є i одиниць.
10.13. Внесіть у бінарне швидке сортування явну перевірку ситуацій, коли всі ключі дорівнюють. Порівняйте час виконання цієї програми з аналогічним показником для стандартної реалізації при N = 10 3 , 10 4 , 10 5 і 10 6 та вхідних даних, описаних у вправі 10.12.