Упорядкування поділом (Quicksort)

Метод упорядкування поділом був запропонований Чарльзом Хоаром [2] в 1962 р. Цей метод є розвитком методу простого обміну і настільки ефективний, що його стали називати "методом швидкого впорядкування - Quicksort".

Основна ідея алгоритму полягає в тому, що випадковим чином вибирається деякий елемент масиву x, після чого масив проглядається ліворуч, поки не зустрінеться елемент a[i] такий, що a[i] > x, а потім масив проглядається праворуч, поки не зустрінеться елемент a[j] такий, що a[j] < x. Ці два елементи міняються місцями, і процес перегляду, порівняння та обміну триває, поки ми не дійдемо до елемента x. У результаті масив виявиться розбитим на дві частини - ліву, у якій значення ключів будуть менші x, і праву зі значеннями ключів, більшими x. Далі процес рекурсивно триває для лівої та правої частин масиву доти, поки кожна частина не буде містити в точності один елемент. Рекурсію можна замінити ітераціями, якщо запам'ятовувати відповідні індекси масиву.

Упорядкування злиттям

Упорядкування зі злиттям, як правило, застосовуються в тих випадках, коли потрібно впорядкувати послідовний файл, що не міститься цілком в основній пам'яті.

Один з популярних алгоритмів внутрішнього впорядкування злиттями базується на наступних ідеях (для простоти будемо вважати, що число елементів у масиві, як і у прикладі, є ступенем числа 2). Спочатку пояснимо, що таке злиття. Нехай є два впорядкованих у порядку зростання масива p[1], p[2],..., p[n] і q[1], q[2],..., q[n], і є порожній масив r[1], r[2],..., r[2! n], який потрібно заповнити значеннями масивів p і q у порядку зростання. Для злиття виконуються наступні дії: рівняються p[1] і q[1], і менше із значень записується в r[1]. Припустимо, що це значення p[1]. Тоді p[2] рівняється з q[1] і менше із значень заноситься в r[2]. Припустимо, що це значення q[1]. Тоді на наступному кроці рівняються значення p[2] і q[2] і т.д., поки ми не досягнемо границь одного з масивів. Тоді остача іншого масиву просто дописується в "хвіст" масиву r.

Для впорядкування злиттям масиву a[1], a[2],..., a[n] заводиться парний масив b[1], b[2],..., b[n]. На першому кроці виробляється злиття a[1] та a[n] з розміщенням результату в b[1], b[2], злиття a[2] і a[n-1] з розміщенням результату в b[3], b[4],..., злиття a[n/2] та a[n/2+1] з переміщенням результату в b[n-1], b[n]. На другому кроці виробляється злиття пар b[1], b[2] та b[n-1], b[n] з переміщенням результату в a[1], a[2], a[3], a[4], злиття пар b[3], b[4] та b[n-3], b[n-2] з переміщенням результату в a[5], a[6], a[7], a[8],..., злиття пар b[n/2-1], b[n/2] та b[n/2+1], b[n/2+2] з переміщенням результату в a[n-3], a[n-2], a[n-1], a[n]. І т.д. На останньому кроці, наприклад (залежно від значення n), виробляється злиття послідовностей елементів масиву довжиною n/2 a[1], a[2],..., a[n/2] та a[n/2+1], a[n/2+2],..., a[n] з переміщенням результату в b[1], b[2],..., b[n].

Для випадку масиву, використаного в наших прикладах, послідовність кроків наведена в табл. 2.5.

Таблиця 2.5

Приклад упорядкування зі злиттям

Початковий стан масиву	8 23 5 65 44 33 1 6
Крок 1	6 8 1 23 5 33 44 65
Крок 2	6 8 44 65 1 5 23 33
Крок 3	1 5 6 8 23 33 44 65

 

При застосуванні впорядкування злиттям число порівнянь ключів і число пересилань оцінюється як O(n! log n). Але варто враховувати, що для виконання алгоритму для впорядкування масиву розміру n потрібно 2! n елементів пам'яті.

Методи зовнішнього впорядкування

Прийнято називати "зовнішнім" упорядкуванням упорядкування послідовних файлів, що розташовуються в зовнішній пам'яті і є занадто великими, щоб можна було повністю перемістити їх в основну пам'ять і застосувати один з розглянутих методів внутрішнього впорядкування. Найчастіше зовнішнє впорядкування застосовується в системах керування базами даних при виконанні запитів, і від ефективності застосовуваних методів істотно залежить продуктивність СУБД.

Методи зовнішнього впорядкування з'явилися, коли найпоширенішими пристроями зовнішньої пам'яті були магнітні стрічки.

Для стрічок чисто послідовний доступ був абсолютно природним. Коли відбувся перехід до запам'ятовувальних пристроїв з магнітними дисками, що забезпечують "прямий" доступ до будь-якого блоку інформації, здавалося, що чисто послідовні файли втратили свою актуальність. Однак це відчуття було помилковим.

Практично всі використовувані в цей час дискові пристрої оснащені рухливими магнітними голівками. При виконанні обміну з дисковим накопичувачем виконується підведення голівок до потрібного циліндра, вибір потрібної голівки (доріжки), прокручування дискового пакета до початку необхідного блоку і, нарешті, читання або запис блоку. Серед всіх цих дій найбільший час займає підведення голівок. Саме цей час визначає загальний час виконання операції. Єдиним доступним прийомом оптимізації доступу до магнітних дисків є як можна більш "близьке" розташування на накопичувачі послідовно адресованих блоків файлу. Але й у цьому випадку рух голівок буде мінімізовано тільки в тому випадку, коли файл читається або пишеться в чисто послідовному режимі. Саме з такими файлами при потребі впорядкування працюють сучасні СУБД.

Насправді швидкість виконання зовнішнього впорядкування залежить від розміру буфера (або буферів) основної пам'яті, що може бути використана для цих цілей.

Розглянемо основні методи зовнішнього впорядкування, що працюють при мінімальних затратах основної пам'яті.

Пряме злиття

Почнемо з того, як можна використати як метод зовнішнього впорядкування алгоритм простого злиття. Припустимо, що є послідовний файл A, що складається із записів a1, a2,..., an (знову для простоти припустимо, що n являє собою ступінь числа 2). Будемо вважати, що кожен запис складається рівно з одного елемента, що представляє собою ключ упорядкування. Для впорядкування використовуються два допоміжних файли B й C (розмір кожного з них буде n/2).

Упорядкування складається з послідовності кроків, у кожному з яких виконується розподіл стану файлу A у файли B і C, а потім злиття файлів B і C у файл A. (Помітимо, що процедура злиття для файлів повністю ілюструється рис. 2.2.14). На першому кроці для розподілу послідовно читається файл A, що складається із записів a1, a3,..., a(n-1) пишуться у файл B, а записи a2, a4,..., an - у файл C (початковий розподіл). Початкове злиття виробляється над парами (a1, a2), (a3, a4),..., (a(n-1), an), і результат записується у файл A. На другому кроці знову послідовно читається файл A, і у файл B записуються послідовні пари з непарними номерами, а у файл C - з парними. При злитті утворяться й пишуться у файл A упорядковані четвірки записів. І так далі. Перед виконанням останнього кроку файл A буде містити дві впорядковані підпослідовності розміром n/2 кожна. При розподілі перша з них потрапить у файл B, а друга - у файл C. Після злиття файл A буде містити повністю впорядковану послідовність записів. У табл.2.2.12 показаний приклад зовнішнього впорядкування простим злиттям.

 

Таблиця 2.6

Приклад зовнішнього впорядкування прямим злиттям

Початковий стан файлу A	8 23 5 65 44 33 1 6
Перший крок Розподіл Файл B Файл C Злиття: файл A	8 5 44 1 23 65 33 6 8 23 5 65 33 44 1 6
Другий крок Розподіл Файл B Файл C Злиття: файл A	8 23 33 44 5 65 1 6 5 8 23 65 1 6 33 44
Третій крок Розподіл Файл B Файл C Злиття: файл A	5 8 23 65 1 6 33 44 1 5 6 8 23 33 44 65

Для виконання зовнішнього впорядкування методом прямого злиття в основній пам'яті потрібно розташувати всього лише дві змінні - для розміщення чергових записів з файлів B і C. Файли A, B і C будуть O(log n) раз прочитані і стільки ж раз записані.

 

Поліпшення ефективності зовнішнього впорядкування за рахунок використання основної пам'яті

Якщо перед початком застосування зовнішнього впорядкування файл містить довгі серії, то менше буде потрібно злиттів і тим швидше закінчиться впорядкування. Тому до початку застосування кожного з методів зовнішнього впорядкування, заснованих на застосуванні серій, початковий файл частинами зчитується в основну пам'ять, до кожної частини застосовується один з найбільш ефективних алгоритмів внутрішнього впорядкування (звичайно Quicksort або Heapsort) і впорядковані частини (утворюючі серії) записуються в новий файл (у старий не можна, тому що він чисто послідовний).

Крім того, звичайно, при виконанні розподілів і злиттів використовується буферизація блоків файлу(ів) в основній пам'яті. Можливий виграш у продуктивності залежить від наявності достатнього числа буферів достатнього розміру.