Швидкі алгоритми сортування

Розглянемо приклад: Нехай  масив A складається з 8 елементів (рис. 2.2).  Другий рядок складається з мінімумів елементів першого рядка, які стоять поруч. Кожний наступний рядок складений з мінімумів елементів, що стоять поруч, попереднього рядка.

 

 

 

 

 

 

Рис 2.2.

Ця структура даних  називається сортуючим деревом. У корені сортуючого дерева розташований найменший елемент. Крім того, у дереві побудовані шляхи елементів масиву від листів до відповідного величині елемента вузла - розгалуження.

Коли дерево побудоване, починається етап просування елементів масиву по дереву. Мінімальний елемент пересилається у вихідний масив B і усі входження цього елемента в дереві заміняються на спеціальний символ M.

 

 

 

 

 

Рис. 2.3.

-17-

Потім здійснюється просування елемента уздовж шляху, відзначеного символом M, починаючи з листка, сусіднього з M і до кореня. Крок просування - це вибір найменшого з двох елементів, що зустрілися на шляху до кореня дерева і його пересилання у вузол, відзначений M. Просування 2-го елемента показано на рис 2.4. (Символ М більше, ніж будь-який елемент масиву).

 

a6 = min(M, a6)

a6 = min(a6, a8)

a3 = min(a3, a6)

b2 = a3

Рис 2.4.

Просування елементів відбувається доти, поки весь вихідний масив не буде заповнений символами M, тобто n раз:

Обґрунтування правильності алгоритму  очевидно, оскільки кожне чергове просування викидає в масив B найменший з елементів масиву А, що залишилися.

 Оцінимо складність алгоритму  в термінах M(n), C(n). Насамперед відзначимо, що даний алгоритм працює однаково на усіх входах, так що його складність у гіршому випадку збігається зі складністю в середньому.

Припустимо, що n - степінь 2 (n = 2^l). Тоді сортуюче дерево має l + 1 рівень (глибину l). Побудова рівня I вимагає n / 2^I порівнянь і пересилань. Таким чином, I-ий етап має складність:

C₁(n) = n/2+n/4+ ... + 2+1 = n-1,  M₁(n) = C₁(n) = n - 1

 

-18-

Для того, щоб оцінити  складність II-го етапу C₂(n) і M₂(n) помітимо, що кожен шлях просування має довжину l, тому кількість порівнянь і пересилань при просуванні одного елемента пропорційно l. Таким чином, M₂(n) = O(l n), C₂(n) = O(l n).

Оскільки l = log₂n, M₂(n)=O(n log₂ n)), C₂(n)=O(n log₂ n), але С(n) = C₁(n) + C₂(n), M(n) = M₁(n) + M₂(n). Тому що C₁(n) < C₂(n), M₁(n) < M₂(n), остаточно одержуємо оцінки складності алгоритму за часом:

M(n) = O(n log₂ n),  C(n) = O(n log₂ n).

У загальному випадку, коли n не є степенем 2, сортуюче дерево будується трохи інакше. “Зайвий” елемент (елемент, для якого немає пари) переноситься на наступний рівень. Легко бачити, що при цьому глибина сортуючого дерева дорівнює [_log2 n] + 1. Удосконалення алгоритму II етапу очевидно. Оцінки при цьому змінюють лише мультиплікативні множники.  Алгоритм має істотний недолік: для нього потрібно додаткова пам'ять розміру 2n - 1.

2.3.2. Пірамідальне сортування

Алгоритм пірамідального сортування також використовує представлення масиву у виді дерева. Цей алгоритм не вимагає допоміжних масивів, сортуючи “на місці”. Розглянемо спочатку метод представлення масиву у виді дерева:

Нехай A - деякий масив розмірності n. Співставимо йому дерево, використовуючи наступні правила:

      

1.A[1] - корінь дерева ;

2.Якщо A[i] - вузол дерева і 2i £ n,

   то A[2*i] - вузол - “лівий син” вузла A[i]

3.Якщо A[i] - вузол дерева і 2i + 1 £ n,

   то A[2*i+1] - вузол - “правий син” вузла A[i] 

Правила 1-3 визначають у масиві структуру дерева, причому глибина дерева не перевершує [log₂ n] + 1. Вони ж задають спосіб руху по дереву від кореня до листків. Рух вгору задається правилом 4:

4.Якщо A[i] - вузол дерева і i > 1,

-19-

 то A[i mod 2] - вузол - “батько” вузла A[i];

Усі рівні дерева, за винятком останнього, цілком заповнені, останній рівень заповнений ліворуч і індексація елементів масиву здійснюється вниз і праворуч. Тому дерево упорядкованого масиву відповідає наступним властивостям: 

A[i] < A[2*i],  A[i] <A[2*i+1],  A[2*i] < A[2*i+1].  (2.1)

Як це не дивно, даний алгоритм спочатку будує дерево, що відповідає прямо протилежним співвідношенням:

A[i] ³ A[2*i], A[i] ³ A[2*i+1]             

а потім змінює місцями A[1] (найбільший елемент) і A[n].

Алгоритм працює в два етапи:

1. побудова сортуючого дерева;

2. просування елементів по сортуючому дереву.

Дерево, що представляє  масив, називається сортуючим, якщо виконуються умови (2.1). Якщо для деякого i ця умова не виконується, будемо говорити, що має місце конфлікт у трикутнику i.

Як на I-ом, так і  на II-ому етапах елементарна дія  алгоритму полягає в вирішенні  конфлікту: якщо найбільший із синів  більше, ніж батько, то переставляються батько і цей син.

У результаті перестановки може виникнути новий конфлікт у  тому трикутнику, куди переставлений батько. У такий спосіб можна говорити про конфлікт у піддереві з коренем у вершині i. Цей конфлікт вирішується послідовним вирішенням конфліктів проходом по дереву вниз. Конфлікт вирішено, якщо прохід закінчився (i > n div 2), або ж в результаті перестановки не виник новий конфлікт. 

Нескладно підрахувати, що С(n) = O( n log₂ n ),   М(n) = O( n log₂ n ).

 

2.3.3. Cортування Хоара

Удосконаливши метод  сортування, який грунтується на обмінах, К. Хоар запропонував алгоритм сортування масивів, що дає на практиці відмінні результати і дуже просто програмується.  Автор назвав свій алгоритм швидким сортуванням.

-20-

Ідея Хоара полягає  в наступному:

1. Виберемо деякий елемент x масиву A випадковим образом;

2. Переглядаємо масив у прямому напрямку (i = 1, 2,...), шукаючи в ньому елемент A[i] не менший за x;

3. Переглядаємо масив у зворотньому напрямку (j = n, n-1,..), шукаючи в ньому елемент A[j] не більший за x;

4.Змінюємо місцями A[i] і A[j];

Пункти 2-4 повторюємо доти, поки i < j;

У результаті такого зустрічного проходу початок масиву A[1..i] і кінець масиву A[j..n] виявляються розділеними “бар'єром” x: A[k] ( x при k < i, A[k] ( x при k > j, причому на поділ ми затратимо не більш n/2 перестановок. Тепер залишилося проробити ті ж дії з початком і кінцем масиву, тобто застосувати їх рекурсивно.

Таким чином, описана  нами процедура залежить від параметрів k та m f – початкового і кінцевого індексів відрізка масиву, який обробляється.

Аналіз складності алгоритму  в середньому, що використовує гіпотезу про рівну імовірність усіх входів, показує, що:

C(n) = O(n log₂ n),  M(n) = O(n log₂ n)

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

2.3.4. Метод цифрового шифрування

Іноді при розв’язанні задач типу задачі сортування можна використовувати особливості типу перетворюваних даних для одержання ефективного алгоритму. Розглянемо одну з таких задач – задачу про звертання підстановки.

Підстановкою множини 1..n назвемо двовимірний масив A[1..2, 1..n] виду

1	2	..........	n-1	n
J1	j2	...........	jn-1	jn

у якому 2-ий рядок містить всі елементи відрізка .  Підстановка B називається зворотньою до підстановки A, якщо B виходить з A сортуванням стовпчиків A у порядку зростання елементів 2-го рядка з наступною

-21-

перестановкою рядків.  Потрібно побудувати алгоритм обчислення зворотньої підстановки. З визначення випливає, що стовпчик [i, j_i] підстановки A потрібно перетворити в стовпчик [j_i , i] і поставити на j_i-те місце в підстановці B.

Складність даної процедури  лінійна, оскільки тіло арифметичного циклу складається з двох операторів присвоювання, в той час як стовпчики підстановки відсортовані.

 

 2.4. Функціональна специфікація

 

2.4.1. Опис фунціональних можливостей

Основною задачею курсової роботи є реалізація швидких методів сортування масивів таких як: сортування деревом, пірамідальне сортування, сортування Хоара та метод цифрового шифрування та їх порівняльна характеристика.

Дане програмне забезпечення має ряд фунціональних можливостей:

1. задання початкових даних (випадковим чином, введених користувачем, прочитаних з файлу);
2. сортування заданого масиву одним із методів:
• пірамідальне сортування;
• сортування деревом;
• сортування Хоара;
• метод цифрового шифрування;
3. сортування заданого масиву одним із способів:
• за зростанням;
• за спаданням;

4) порівняння різних методів сортування за швидкодією і за складністю.

Тому основним функціональним призначення розробленої програми є забезпечення можливості проведення вищезазначених пунктів. Результати роботи програмного забезпечення дозволяють провести порівняльний аналіз швидких методів сортування масивів.

 

 

-22-

2.4.2. Опис інтерфейсу користувача

Інтерфейс програми складається  з форми на якій розміщено засоби керування програмою, засоби візуалізації даних (рис 2.5).

   

Рис 2.5. Інтерфейс програми

 

Користувач може задати вхідний масив (пункт меню “Дані”) одним з 3 способів: випадковим чином, введенням вручну, читанням з файлу.

Пункт меню “Метод сортування” дозволяє вибрати один з методів сортування (пірамідальне сортування, сортування деревом, сортування Хоара, метод цифрового шифрування).

Пункт меню “Тип сортування” дозволяє вибрати один зі способів сортування (за зростанням, за спаданням).

Пункт меню “Дії” дозволяє або відсортувати заданий масив одним способом, або провести порівняльну характеристику вищенаведених способів на заданому масиві.

 

 

-23-

2.4.3. Діаграма прецедентів різних режимів роботи

Діаграми прецедентів (можливостей користувача) для різних режимів роботи подано на рис 2.6.

Рис.2.6. Діаграма прецедентів.

 

2.5. Технічна  специфікація

 

2.5.1. Опис діаграми модулів

Діаграма модулів представляє  собою взаємозвязні юніти середовища програмування Borland C++Builder 6.0, всього, у програмі, їх є 3.

Головним модулем програми є Unit 1, в якому реалізовані методи швидкого сортування масивів, введення початкових даних, виведення результатів сортування та керування процесом роботи програми.

Другим модулем є Unit 2, в якому реалізовано задання кількості елементів масиву та їх діапазон при заданні масиву випадковим чином.

Третім моделем є Unit 3, в якому реалізовано вивід результатів порівняльної характеристики методів швидкого сортування.

 

-24-

Сукупність модулів  програми представлено у вигляді  головного вікна програми, яке  зображено на рис 2.5.

 

2.5.2. Опис і обгрунтування вхідних та вихідних даних

Вхідними даними можна вважати: масив дійсних чисел та його розмірність, метод сортування (сортування деревом, пірамідальне сортування, сортування Хоара чи метод цифрового шифрування), тип сортування (за зростанням чи за спаданням).

Вихідними даними програми є: відсортований масив, час затрачений на сортування, кількість операцій порівняння та присвоєння.

 

 

-25-

3. КОНСТРУЮВАННЯ  ПРОГРАМНОГО ЗАБЕЗПЕЧЕННЯ

 

3.1. Опис та  обгрунтування обраних програмних  засобів

 Програмне забезпечення розроблене та відлагоджене за допомогою компілятора Borland C++Builder 6.0. Функціонування такої програми можливе в операційних системах на платформі Windows (98/NT/ME/2000/XP). Даний програмний продукт не використовує жодного додаткового програмного забезпечення, тому його функціонування забезпечується засобами операційної системи Windows.

 

3.2. Опис програми

Програмне забезпечення Sort складається з одного самостійного файлу Project1.exe.

Запуск відбувається подвійним натисканням лівої  клавіші миші на ярлиці програми. На екрані користувач побачить наступне (рис 3.1.)

Рис 3.1. Головн форма програми

 

-26-

Користувач може задати початкові дані одним зі 3 способів: випадковим чином, введенням вручну, читанням з файлу, який можна вибрати  в пункті меню “Дані”:

Рис 3.2. Задання початкових даних