Порівняльний аналіз ефективності та складності швидких алгоритмів сортування масивів (стр. 4 из 5)
При першому проходженні Quick Sort порівнює всі елементи з ведучим і виконується не більше ніж за C*N кроків, де C - деяка константа. Потім потрібно відсортувати дві підпослідовності довжинами I-1 та N-I. Тому середня кількість кроків, потрібних для впорядкування N елементів, залежить від середньої кількості кроків, потрібних для впорядкування I-1 та N-I елементів відповідно. Оскільки всі можливі значення
є рівноймовірними, то спрведлива наступна оцінка : 
.Врахувавши, що
,отримаємо
.(1)Покажемо за індукцією по N, що
для 
, де K=2C+2B, B=Q(0)=Q(1). Останнє співвіднощення означає, що Quick Sort вимагає постійної однакової кількості кроків для впорядкування 0 або 1 елемента.1) N=2 :
;2) припустимо, що
для I=2, 3, ..., N-1 ;3) перевіримо справедливість для I=N. Співвідношення (1) з врахуванням попереднього припущення можна переписати у вигляді
або 
.(2)Оскільки функція I*ln(I) є опуклою вниз, то для цілих значень аргументу справедлива оцінка
Врахувавши останню нерівність, із співвідношення (2) одержимо
.Оскільки
, то 
.Остаточно отримаємо
.(3)Таким чином ефективність алгоритму Quick Sort є величина порядку O(N*ln(N)).
Всі наведені викладки справедливі для аналізу по операціях порівняння. Кількість же перестановок залежить від початкового розміщення елементів у послідовності. Характерно, що для цього методу у випадку зворотньо впорядкованого масиву об’єм переміщень ключів не буде максимальним. Адже на кожному етапі ведучий елемент буде найбільшим і опиниться на своєму місці після першого ж порівняння і перестановки, тобто M=N-1. Максимальна кількість переприсвоєнь ключів співпадатиме з кількістю порівнянь, мінімальна - рівна нулю.
Алгоритм Quick Sort, як і розглянуті прямі методи, описує процес стійкого сортування.
2.3 Сортування вибором при допомозі дерева – алгоритм ТreeSort
Алгоритм сортування деревом ТreeSort власне кажучи є поліпшенням алгоритму сортування вибором. Процедура вибору найменшого елемента удосконалена як процедура побудови так званого сортуючого дерева. Сортуюче дерево - це структура даних, у якій представлений процес пошуку найменшого елемента методом попарного порівняння елементів, що стоять поруч. Алгоритм сортує масив у два етапи.
I етап : побудова сортуючого дерева;
II етап : просівання елементів по сортуючому дереву.
Розглянемо приклад: Нехай масив A складається з 8 елементів. Другий рядок складається з мінімумів елементів першого рядка, які стоять поруч. Кожний наступний рядок складений з мінімумів елементів, що стоять поруч, попереднього рядка.
Ця структура даних називається сортуючим деревом. У корені сортуючого дерева розташований найменший елемент. Крім того, у дереві побудовані шляхи елементів масиву від листів до відповідного величині елемента вузла -розгалуження.
Коли дерево побудоване, починається етап просівання елементів масиву по дереву. Мінімальний елемент пересилається у вихідний масив B і усі входження цього елемента в дереві заміняються на спеціальний символ M. Потім здійснюється просівання елемента уздовж шляху, відзначеного символом M, починаючи з листка, сусіднього з M і до кореня. Крок просівання - це вибір найменшого з двох елементів, що зустрілися на шляху до кореня дерева і його пересилання у вузол, відзначений M.
a6 = min(M, a6)
a6 = min(a6, a8)
a3 = min(a3, a6)
b2 := a3
Просівання елементів відбувається доти, поки весь вихідний масив не буде заповнений символами M, тобто n раз:
For і := 1 to n do begin
Відзначити шлях від кореня до листка символом M;
Просіяти елемент уздовж відзначеного шляху;
B[I] := корінь дерева
end;
Обґрунтування правильності алгоритму очевидно, оскільки кожне чергове просівання викидає в масив У найменший з елементів масиву А, що залишилися.
Сортуюче дерево можна реалізувати, використовуючи або двовимірний масив, або одномірний масиві ST[1..N], де N = 2n-1.
Аналіз алгоритму TreeSort.
Оцінимо складність алгоритму в термінах M(n), C(n). Насамперед відзначимо, що алгоритм Tree Sort працює однаково на усіх входах, так що його складність у гіршому випадку збігається зі складністю в середньому.
Припустимо, що n - ступінь 2 (n = 2l). Тоді сортуюче дерево має l + 1 рівень (глибину l). Побудова рівня I вимагає n / 2I порівнянь і пересилань. Таким чином, I-ий етап має складність:
C1(n) = n/2+n/4+ ... + 2+1 = n-1, M1(n) = C1(n) = n - 1
Для того, щоб оцінити складність II-го етапу С2(n) і M2(n) помітимо, що кожен шлях просівання має довжину l, тому кількість порівнянь і пересилань при просіванні одного елемента пропорційно l. Таким чином,
M2(n) = O(l n),
C2(n) = O(l n).
Оскільки l = log2n, M2(n)=O(n log2 n)), C2(n)=O(n log2 n), Але З(n) = C1(n) + C2(n), M(n) = M1(n) + M2(n). Тому що C1(n) < C2(n), M1(n) < M2(n),остаточно одержуємо оцінки складності алгоритму Tree Sort за часом:
M(n) = O(n log2 n), C(n) = O(n log2 n),
У загальному випадку, коли n не є ступенем 2, сортуюче дерево будується трохи інакше. "Зайвий" елемент (елемент, для якого немає пари) переноситься на наступний рівень. Легко бачити, що при цьому глибина сортуючого дерева дорівнює [log2 n] + 1. Удосконалення алгоритму II етапу очевидно. Оцінки при цьому змінюють лише мультиплікативні множники. Алгоритм Tree Sort має істотний недолік: для нього потрібно додаткова пам'ять розміру 2n - 1.
2.4Сортування вибором при допомозі дерева – алгоритм HeapSort
Прямий вибір - повторюваний пошук найменшого елемента серед N елементів, N-1 елементів, N-2 і т.д. Кількість порівнянь при цьому (N2-N)/2. Для підвищення ефективності необхідно залишати після кожного етапу побільше інформації окрім ідентифікації найменшого ключа.
Після N/2 порівнянь можна знайти в кожній парі елементів найменший, після N/4 порівнянь - менший із пари вже вибраних на попередньому кроці і т.д. Виконавши загалом N/2+N/4+...+2+1=N-1 порівнянь, можна побудувати дерево вибору та ідентифікувати його корінь як шуканий найменший елемент. Наприклад
крок I \ / \ / \ / \ /
44 12 06
крок II \ / \ /
12 06
крок III \ /
06
На наступному етапі сортування проводиться рух вздовж віток, які відмічені мінімальними елементом, і вилучення його з дерева шляхом заміни на пустий елемент.
44[]
\ / \ / \ / \ /
44 12 18 []
\ / \ /
12 []
\ /
[]
Далі здійснюється заповнення "дірок" у дереві. На першому рівні залишається "дірка" від вилученого елемента, а на наступних знову вибирається менший із двох сусідніх попереднього рівня. "Дірка" при порівнянні вважається як завгодно великим значенням.
44[]
\ / \ / \ / \ /
44 12 18 67
\ / \ /
12 18
\ /
12
Елемент, що опинився в корені, - знову найменший. Після N таких кроків дерево стане пустим, в ньому будуть лише одні "дірки" (сортування закінчене). На кожному з N етапів виконується log(N) порівнянь. Тому на весь процес впорядкування потрібно порядку N*log(N) операцій плюс N-1 операцій для побудови дерева. Це значно краще ніж N2 для прямих методів і навіть краще ніж N1,2 для алгоритму Шелла. Однак при цьому виникає проблема збереження додаткової інформації. Тому кожен окремий етап в алгоритмі ускладнюється.
Корисно було б, зокрема, позбутися від "дирок", якими вкінці буде заповнене все дерево, і які породжують багато непотрібних порівнянь. Крім того, виникає потреба такої організації даних за принципом дерева, яка б вимагала N одиниць пам’яті, а не 2N-1. Цього вдалося добитися в алгоритмі Heap Sort, який розробив Д. Уілльямс. Він використав спеціальну деревовидну структуру - піраміду.
Піраміда - це означене, тобто задане елементами кореневе бінарне дерево, яке визначається як послідовність ключів a L , a L+1 , ..., a R , для якої справедливі нерівності
та 
для 
.(1)Таким чином бінарне дерево сортувань виду
a1
/ \
a2=42a3=06
/ \ / \
a4=55a5=94a6=18a7=12
являєсобоюпіраміду, аелементa1буденайменшимврозглядуваніймножині : a1=min(a 1 , a 2 , ..., a N).
Припустимо, щоєдеякапірамідаіззаданимиелементамиa L+1 , ..., a R дляпевнихзначеньLта R, іпотрібноввестиновийелементx, утворюючитакимчиномрозширенупірамідуa L , a L+1 , ..., a R . Вякостівихідноївізьмемопірамідуa 1 , a 2 , ..., a 7ізпопередньогоприкладуідобавимодонеїзліваелементa 1=44. Нова піраміда отримується так : спочатку x ставиться зверху деревовидної структури, а потім він поступово опускається вниз кожен раз в напрямку меншого з двох прилеглих до нього елементів, а сам цей менший елемент переміщується вгору. Процес просіювання продовжується доти, поки в жодній з прилеглих вершин не буде елемента меншого за нововведеного. В розглядуваному прикладі ключ 44 спочатку поміняється місцями з ключем 06, а потім з 12, і в результаті отримується таке дерево