Курсовая работа: Порівняльний аналіз ефективності та складності швидких алгоритмів сортування масивів

Розглянемо приклад: Нехай масив 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 .

Аналіз алгоритму Tree Sort .

Оцінимо складність алгоритму в термінах 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Сортування вибором при допомозі дерева – алгоритм Heap Sort

Прямий вибір - повторюваний пошук найменшого елемента серед N елементів, N-1 елементів, N-2 і т.д. Кількість порівнянь при цьому (N² -N)/2 . Для підвищення ефективності необхідно залишати після кожного етапу побільше інформації окрім ідентифікації найменшого ключа.

Після N/2 порівнянь можна знайти в кожній парі елементів найменший, після N/4 порівнянь - менший із пари вже вибраних на попередньому кроці і т.д. Виконавши загалом N/2+N/4+...+2+1=N-1 порівнянь, можна побудувати дерево вибору та ідентифікувати його корінь як шуканий найменший елемент. Наприклад

крок I \ / \ / \ / \ /