МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
Херсонський Державний Педагогічний Університет
Фізико-математичний факультет
Кафедра інформаційних технологій
Швидкі алгоритми сортування
Курсова робота
Виконавець
Керівник
Херсон 2001
Зміст
< br>Вступ 3
1. Аналіз швидких алгоритмів сортування 6
1.1. Сортування деревом 6
1.2. Пірамідальне сортування 9
1.3 Швидке сортування Хоар 12
1.4 Метод цифрового сортування 14
2. Практична реалізація мовою Паскаль швидких алгоритмів сортування 16
Висновки 22
Список використаних джерел 24
Вступ
У наш час нові інформаційні технології посідають дуже важливе місце нелише в спеціалізованих, але й в повсякденних сферах життя. Комп'ютеризастосовуються в бізнесі, менеджменті, торгівлі, навчанні та багатьохінших сферах діяльності людини.
Комп'ютерні технології дуже зручні для виконання різноманітнихоперацій, але в різних сферах застосування ці операції різні. Тому, кожнаокрема галузь, яка використовує специфічні технічні засоби, потребує своїхвласних програм, які забезпечують роботу комп'ютерів.
Розробкою програмного забезпечення займається така галузь науки, якпрограмування. Вона набуває все більшого й більшого значення останнімчасом, адже з кожним днем комп'ютер стає все більш необхідним, все більшповсякденним явищем нашого життя. Адже обчислювальна техніка минулих роківвже майже повністю вичерпала себе і не задовольняє тим потребам, щопостають перед людством.
Таким чином, нові інформаційні технології дуже актуальні внаш час і потребують багато уваги для подальшої розробки та вдосконалення.
Поряд з цим, велике значення має також і програмування, яке є одним ізфундаментальних розділів інформатики і тому не може залишатись осторонь.
Програмування містить цілу низку важливих внутрішніх задач. Однією знайбільш важливих таких задач для програмування є задача сортування. Підсортування звичайно розуміють перестановки елементів будь-якоїпослідовності у визначеному порядку. Ця задача є однією з найважливішихтому, що її метою є полегшення подальшої обробки певних даних і,насамперед, задачі пошуку. Так, одним з ефективних алгоритмів пошуку єБінарний пошук. Він працює швидше ніж, наприклад, лінійний пошук, але йогоможливо застосовувати лише за умови, що послідовність вже упорядкована,тобто відсортована.
Взагалі, відомо, що в будь-якій сфері діяльності, що використовуєкомп'ютер для запису, обробки та збереження інформації, усі данізберігаються в базах даних, які також потребують сортування. Певнавпорядкованість для них дуже важлива, адже користувачеві набагато легшепрацювати з даними, що мають певний порядок. Так, можна розташувати всітовари по назві або відомості про співробітників чи студентів за прізвищемабо роком народження, тощо.
Задача сортування в програмуванні не вирішена повністю. Адже, хоча йіснує велика кількість алгоритмів сортування, все ж таки метоюпрограмування є не лише розробка алгоритмів сортування елементів, але йрозробка саме ефективних алгоритмів сортування. Ми знаємо, що одну й тусаму задачу можна вирішити за допомогою різних алгоритмів і кожен раз змінаалгоритму приводить до нових, більш або менш ефективних розв'язків задачі.
Основними вимогами до ефективності алгоритмів сортування є перш за всеефективність за часом та економне використання пам'яті. Згідно цих вимог,прості алгоритми сортування (такі, як сортування вибором і сортуваннявключенням) не є дуже ефективними.
Алгоритм сортування обмінамі, хоча і завершує свою роботу (оскільки вінвикористовує лише цикли з параметром і в тілі циклів параметри примусово НЕзмінюються) і не використовує допоміжної пам'яті, але займає багато часу.
Навіть, якщо внутрішній цикл не містить жодної перестановки, то дії будутьповторюватись до тих пір, поки не завершиться зовнішній цикл.
Алгоритм сортування вибором ефективніше сортування обмінамі закритерієм М (n), тобто за кількістю пересилання, але також є не дужеефективним. З цих причин було розроблено деякі нові алгоритми сортування,що отримали назву швидких алгоритмів сортування. Це такі алгоритми, яксортування деревом, пірамідальне сортування, швидке сортування Хоар таметод цифрового сортування.
Метою нашої дослідницької роботи є ознайомлення з цими швидкимиалгоритмами сортування, спроба проаналізувати їх і висвітлити кожен з них інаписати програму, яка б виконувала сортування деякої послідовності задопомогою різних швидких алгоритмів сортування.
1. Аналіз швидких алгоритмів сортування
1.1. Сортування деревом
Алгоритм сортування деревом ТreeSort власне кажучи є поліпшеннямалгоритму сортування вибором. Процедура вибору найменшого елементаУдосконалена як процедура побудови т.зв. сортуючого дерева. Сортуюче дерево
- Це структура даних, у якій представлений процес пошуку найменшогоелемента методом попарного порівняння елементів, що стоять поруч. Алгоритмсортує масив у два етапи.
I етап: побудова сортуючого дерева;
II етап: просівання елементів по сортуючому дереву.
Розглянемо приклад: Нехай масив A складається з 8 елементів (мал. 1, 1 --а рядок). Другий рядок складається з мінімумів елементів першого рядка,які стоять поруч. Кожний наступний рядок складений з мінімумів елементів,що стоять поруч, попереднього рядка.
Ця структура даних називається сортуючім деревом. У корені сортуючогодерева розташований найменший елемент. Крім того, у дереві побудовані шляхиелементів масиву від листів до відповідного величині елемента вузла --розгалуження. (На мал.1 шлях мінімального елемента a5 - від листа a5 докореня відзначений товстою лінією.)
Коли дерево побудоване, починається етап просівання елементів масиву подереву. Мінімальний елемент пересилається у вихідний масив B і усівходження цього елемента в дереві заміняються на спеціальний символ M.
Потім здійснюється просівання елемента уздовж шляху, відзначеногосимволом M, починаючи з листка, сусіднього з M (На мал 2. униз) і докореня. Крок просівання - це вибір найменшого з двох елементів, щозустрілися на шляху до кореня дерева і його пересилання у вузол,відзначений M. Просівання 2-го елемента показано на мал 3. (Символ Мбільше, ніж будь-який елемент масиву).
a6 = min (M, a6) a6 = min (a6, a8) a3 = min (a3, a6) b2: = a3 < p> Просівання елементів відбувається доти, поки весь вихідний масив НЕбуде заповнений символами M, тобто n раз:
For I: = 1 to n do begin
Відзначити шлях від кореня до листка символом M;
Просіяті елемент уздовж відзначеного шляху;
B [I]: = корінь дерева
end;
Обгрунтування правильності алгоритму очевидно, оскільки кожне черговепросівання викидає в масив У найменший з елементів масиву А, що залишилися.
Сортуюче дерево можна реалізувати, використовуючи або Двовимірниймасив, або одномірній масиві ST [1 .. N], де N = 2n-1 (див. наступний розділ).
Оцінимо складність алгоритму в термінах M (n), C (n). Насамперед відзначимо,що алгоритм TreeSort працює однаково на усіх входах, так що його складністьу гіршому випадку збігається зі складністю в середньому.
Припустимо, що 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 (ln).
Оскільки 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) M (n) = O (n log2 n), C (n) = O (n log2 n),
У загальному випадку , коли n не є ступенем 2, сортуюче дерево будуєтьсятрохи інакше. "Зайвий" елемент (елемент, для якого немає пари) переноситьсяна наступний рівень. Легко бачити, що при цьому глибина сортуючого деревадорівнює [log2 n] + 1. Удосконалення алгоритму II етапу очевидно. Оцінкипри цьому змінюють лише мультіплікатівні множник. Алгоритм TreeSort маєістотний недолік: для нього потрібно додаткова пам'ять розміру 2n - 1.
1.2. Пірамідальне сортування
Алгоритм пірамідального сортування HeapSort також використовуєпредставлення масиву у виді дерева. Цей алгоритм не вимагає допоміжнихмасивів, сортуючі "на місці". Розглянемо спочатку метод представленнямасиву у виді дерева:
Нехай A [1 .. 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 визначають у масиві структуру дерева, причому глибинадерева не перевершує [log2 n] + 1. Вони ж задають спосіб руху по дереву відкореня до листків. Рух вгору задається правилом 4:
4.Якщо A [i] - вузол дерева і i> 1, то A [i mod 2] - вузол - "батько" вузла A [i];
Приклад: Нехай A = [45 13 24 31 11 28 49 40 19 27] - масив. Відповіднейому дерево має вигляд:
Зверніть увагу на те, що всі рівні дерева, за винятком останнього,цілком заповнені, останній рівень заповнений ліворуч і індексація елементівмасиву здійснюється вниз і праворуч. Тому дерево упорядкованим масивувідповідає наступним властивостям:
A [i] (A [2 * i], A [i] (A [2 * i +1], A [2 * i] (A [2 * i + 1].
Як це не дивно, алгоритм HeapSort спочатку будує дерево, що відповідаєпрямо протилежним співвідношенням:
A [i] (A [2 * i], A [i] (A [2 * i +1]а потім змінює місцями A [1] (найбільший елемент) і A [n].
Як і TreeSort, алгоритм HeapSort працює в два етапи:
I. Побудова сортуючого дерева;
II. Просівання елементів по сортуючому дереву.
Дерево, що представляє масив, називається сортуючім, якщо виконуютьсяумови (6). Якщо для деякого i ця умова не виконується, будемо говорити, щомає місце (сімейний) конфлікт у трикутнику i.
Як на I-му, так і на II-ому етапах елементарна дія алгоритму полягає ввирішенні сімейного конфлікту: якщо найбільший із синів більше, ніж батько,то переставляються батько і цей син (процедура ConSwap).
У результаті перестановки може виникнути новий конфлікт у томутрикутнику, куди переставлений батько. У такий спосіб можна говорити проконфлікт (роду) у піддереві з коренем у вершині i. Конфлікт родувирішується послідовним вирішенням сімейних конфліктів проходом по деревувниз. (На мал шлях вирішення конфлікту роду у вершині 2 відзначений).
Конфлікт роду вирішено, якщо прохід закінчився (i> n div 2), або ж урезультаті перестановки не виник новий сімейний конфлікт (процедура
Conflict).
Procedure ConSwap (i, j: Integer);
Var b: Real;
Begin
If a [ i]
End;
Procedure Conflict (i, k: Integer);
Var j: Integer;
Begin j: = 2 * i ;
If j = k then ConSwap (i, j) else if j a [j] then j: = j + 1; ConSwap (i, j); Conflict (j, k) end
End;
I етап - побудова сортуючого дерева - оформимо у виді рекурсівноїпроцедури, використовуючи визначення:
Якщо ліве і праве піддерева T (2i) і T (2i +1) дерева T (i) є сортуючімі,то для перебудови T (i) необхідно вирішити конфлікт роду в цьому дереві.
Procedure SortTree (i: Integer); begin
If ij, причому на поділ ми затратімо не більш n/2перестановок. Тепер залишилося проробити ті ж дії з початком і кінцеммасиву, тобто застосувати їх рекурсивно.
Таким чином, описана нами процедура Hoare залежить від параметрів k таm - початкового і кінцевого індексів відрізка масиву, який обробляється.
Procedure Swap (i, j: Integer);
Var b: Real;
Begin b : = a [i]; a [i]: = a [j]; a [j]: = b
End;
Procedure Hoare (L, R: Integer) ;
Var left, right: Integer; x: Integer;
Begin
If L Repeat (зустрічний прохід)
While A [left] While A [right]> x do Dec (right); (перегляд назад)
If left right;
Hoare (L, right); (сортуємо початок)
Hoare (left, R) (сортуємо кінець) end
End;
Program QuickSort;
Const n = 100;
Var A: array [1 .. n] of Integer;
(процедури Swap, Hoare, введення і висновку)
Begin
Inp; Hoare (1, n); Out
End.
Аналіз складності алгоритму в середньому, що використовує гіпотезу прорівну імовірність усіх входів, показує, що:
C (n) = O (n log2 n), M (n) = O (n log2 n)
У гіршому випадку, коли в якості бар'єрного вибирається, наприклад,максимальний елемент підмассіву, складність алгоритму квадратична.
1.4 Метод цифрового сортування
Іноді при розв'язанні задач типу задачі сортування можнавикористовувати особливості типу перетворювання даних для одержанняефективного алгоритму. Розглянемо одну з таких задач - задачу про звертанняпідстановкі.
Підстановкою безлічі 1 .. n назвемо Двовимірний масив A [1 .. 2, 1 .. n] виду
| 1 | 2 |........| n-1 | n |
| | | .. | | |
| J1 | j2 |........| jn-1 | jn |
| | | ... | | |
у якому 2-ий рядок містить всі елементи відрізка 1 .. n. Підстановка Bназивається зворотньою до підстановкі A, якщо B виходить з A сортуваннястовпчиків A у порядку зростання елементів 2-го рядка з наступноюперестановка рядків. Потрібно побудувати алгоритм обчислення зворотньоїпідстановкі. З визначення випливає, що стовпчик [i, ji] підстановкі Aпотрібно перетворити в стовпчик [ji, i] і поставити на ji-те місце впідстановці B.
(Type NumSet = 1 .. n;
Substitution = array [1 .. 2, NumSet] of NumSet;)
Procedure Reverse (Var A, B: Substitution);
Begin
For i: = 1 to n do begin
B [A [2, i], 2 ]: = i; B [A [2, i], 1]: = A [2, i] end
End;
Складність процедури Reverse лінійна, оскільки тіло арифметично циклускладається з двох операторів прісвоювання, в той час як стовпчикипідстановкі відсортовані.
2. Практична реалізація мовою Паскаль швидких алгоритмів сортування
Практично метою нашої дослідницької роботи було написання мовою
Pascal програми, яка б виконувала сортування будь-якої послідовностіелементів. Для того, щоб продемонструвати роботу різних швидких алгоритмівсортування, ми залишили вибір конкретного алгоритму на розсуд користувачапрограми. Тобто, ми створили основну програму - меню, яка пропонуєкористувачеві три можливі варіанти швидких алгоритмів сортування: швидкесортування, сортування Хоар та сортування "злиттям". Вибір певногоалгоритму здійснюється за допомогою оператору "case of", тобто натисканнямклавіш клавіатури 1, 2 або 3. Також ми передбачили варіант, коли користувачпрограми натискає будь-яку іншу клавішу: в цьому випадку на екраніз'явиться повідомлення про помилку. Також, після проведення сортування завибраним алгоритмом, користувач зможе продовжити роботу й випробувати іншийалгоритм. Для цього потрібно натиснути клавіші клавіатури "у" або "д" абонабрати слово "yes" чи "так" коли після завершення роботи одного з обранихалгоритмів сортування на екрані з'явиться запитання "Чи хочете випродовжити роботу з даною програмою? ". Якщо ж користувач уже випробувавусі алгоритми або за браком часу (або бажання) хоче завершити роботу зпрограмою, то йому достатньо буде лише натиснути на клавіатурі клавіші "n"або "н" чи набрати слова "no" або "ні" після того, як на екраніз'явиться зазначене вище запитання.
Програма виконує сортування послідовності за трьома алгоритмамисортування. Кожний окремий алгоритм представлений у вигляді окремоїпроцедури.
Так, процедура Qsort виконує швидке сортування масиву, що вводиться.
Під час роботи цього алгоритму відбувається аналіз даної послідовностіодночасно у двох напрямках (зліва-направо і зправа-наліво). комп'ютерпорівнює два елементи, що стоять поряд зліва. Якщо ці елементи стоять насвоїх місцях, тобто перший з них є меншим за другий, то комп'ютер порівнюєперший елемент з останнім. Якщо при порівнянні останній елемент виявитьсяменшим за перший, то комп'ютер виконає перестановку цих двох елементів.
Такі дії будуть відбуватися до тих пір, поки індикатор, якій відповідає заліву частину послідовності (в нашій процедурі це "i") не перейде на правучастину, а індикатор, що відповідає за праву частину масиву (в нашійпроцедурі це "j") не перейде на праву частину. Далі та ж сама процедуравикликається рекурсивно. Тобто, якщо ліва частина вже відсортована, то миВикликаємо ту саму процедуру і комп'ютер виконує ті самі дії, але впараметрах процедури ми змінюємо ліву границю. Те саме відбувається, коливідсортована права частина масиву.
По суті цей алгоритм працює на основі алгоритму сортування обмінамі,але цей алгоритм вважається швидким, оскільки перегляд послідовностівідбувається у двох напрямках одночасно. Реалізовано ж цей алгоритм задопомогою оператору "if", який відповідає за порівняння елементів, тапересилання.
Procedure _Qsort (var a: mas; low, hi: byte);
Var i, j: byte; begin if hi> low then begin i: = low; j: = hi; x: = a [i];
While i HoareSearch (L, right);
HoareSearch (left, R); end;
End;
Також у програмі представлена процедура, яка відповідає за введеннямасиву. Вона не винесена окремо в головну програму і користувач не побачитьїї на своєму екрані-меню. Він побачить лише ті три сортування, що написаніу вигляді процедур.
В своїй роботі минаписали програму, що сортує масив за допомогою лишетрьох алгоритмів сортування. Але можна створити процедури, які б містилиалгоритми сортування деревом та пірамідального сортування. Це не вплинедуже суттєво на нашу програму. Потрібно буде лише додати ці процедуриоператор "Case of" головної програми і користувач зможе обирати їх івикористовувати їх так само, як і ті алгоритми, що вже були розглянуті намив нашій дослідницькій роботі.
Висновки
Отже, ми розглянули як працюють швидкі алгоритми сортування іспробували визначити їх складність.
Застосування того чи іншого алгоритму сортування для вирішенняконкретної задачі є досить складною проблемою, вирішення якої потребує нелише досконалого володіння саме цим алгоритмом, але й всебічногорозглядання того чи іншого алгоритму, тобто визначення усіх його переваг інедоліків.
Звичайно, необхідність застосування саме швидких алгоритмів сортуванняочевидна. Адже прості алгоритми сортування не дають бажаної ефективності вроботі програми. Але завжди треба пам'ятати й про те, що кожний швидкийалгоритм сортування поряд із своїми перевагами може містити і деякінедоліки.
Так, алгоритм сортування деревом, хоча й працює однаково на всіх входах
(так, що його складність в гіршому випадку співпадає зі складністю всередньому), але цей алгоритм має і досить суттєвий недолік: для ньогопотрібна додаткова пам'ять розміром 2n-1.
Розглядаючи такий швидкий алгоритм сортування, як пірамідальнесортування, можна зазначити, що цей алгоритм ефективніший ніж попередній,адже він сортує "на місці", тобто він не потребує додаткових масивів.
Крім того, цей алгоритм ( "з точністю до мультіплікатівної константи" (4,
74)) оптимальний: його складність співпадає з нижньою оцінкою задачі,тобто за критеріями C (n) та M (n) він має складність O (n log2 n), алемістить складний елемент в умові. Тобто, в умові A [left] має бути строгоменше ніж x, а A [right] - строго більше за x. Якщо ж замість "строгобільше "та" строго менше "поставити знаки, що позначають" більше, абодорівнює "та" менше, або дорівнює ", то індекси left і right пробіжатьувесь масив і побіжать далі. Вийти з цієї ситуації можна було б шляхомускладнення умов продовження перегляду, але це б погіршило ефективністьпрограми.
У нашій роботі ми розглянули деякі швидкі алгоритми сортування та їхреалізацію мовою Pascal, дослідили не лише переваги таких алгоритмів,ефективність їх використання, але й визначили деякі недоліки окремихалгоритмів, що заважають вживати їх для вирішення першої ліпшої задачісортування.
Отже, головною задачею, яку має вирішити людина, яка повинна розв'язатизадачу сортування - це визначення як позитивних, так і усіх негативниххарактеристик різних алгоритмів сортування, передбачення кінцевогорезультату. До того ж, треба враховувати головне - чи, можливо, цюзадачу задовольнить один з класичних простих алгоритмів сортування.
Список використаних джерел
1. Абрамов С. А., Зима Е. В. Начала програмування мовою
Pascal. - М.: Наука, 1987.
2. Абрамов В. Г. Введение в мову Pascal: Навчальний посібник для студентів вузів за фахом Прикладна математика. - М.: Наука, 1988.
3. Джонс Ж., Харроу К. Рішення завдань у системі Турбо-Паскаль/Переклад з англійської Уланова, Широкого. - М.: Фінанси і статистика, 1991.
4. Зуев Е. А. Мова програмування Турбо Паскаль 6.0, 7.0. - М.: Радіо і зв'язок, 1993.
5. Культин Н. Б. Програмування в TurboPascal 7.0 і Delphi. - Санкт-петербург, 1999.
6. Львов М. С., Співаковський О. В. Основи алгоритмізації та програмування.
- Херсон, 1997.
7. Пермінов О. М. Програмування на мові Паскаль. - М.: Радіо і зв'язок,
1988.
8. Пермінов О. Н. Мова програмування Pascal. - М.: Радіо і свіязь, 1989.
9. Турбо Паскаль 7.0 Издание 10-е стереотипне. - Санкт-Петербург:
"Друкарський Двір", 1999.
10. Фаронов В. В. TurboPascal 7.0. Початковий курс. - М.: "Нолидж", 2000.
----------------------- a1
a2
a3
a4
a5
a6
a7
a8
a2
a3
a5
a8
a3
a5 < p> a5
a2 = min (a1, a2) a3 = min (a3, a4) a5 = min (a5, a6) a8 = min (a7, a8)
a3 = min (a2, a3) a5 = min (a5, a8)
a5 = min (a3, a5)
малий 1
a1
a2
a3
a4
M
a6
a7 < p> a8
a2
a3
M
a8
a3
M
M
a5
a3
a4
M
a6
a7
a8
a3
a6
a8
a3
a6
a3
a1
a2
a2
a5 a3
A [2i]
A [2i +1]
A [i]
45
13
24
31
11
28
49
40 < p> 19
27
В
малий 2
