Реферат: Быстрые алгоритмы сортировки

МІНІСТЕРСТВО НАУКИ ІОСВІТИ УКРАЇНИ

Херсонський ДержавнийПедагогічний Університет

Фізико-математичнийфакультет

Кафедра інформаційнихтехнологій

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

Курсова робота

Виконавець

Керівник

Херсон 2001

Зміст

Вступ… 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-а рядок). Другийрядок складається з мінімумів елементів першого рядка, які стоять поруч. Кожнийнаступний рядок складений з мінімумів елементів, що стоять поруч, попередньогорядка.

/> /> /> /> /> /> /> /> <td/>

мал 1

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

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

/> /> /> /> /> /> /> /> /> /> />

/> <td/>

мал 2

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

a6 =min(M, a6)

a6 =min(a6, a8)

a3 =min(a3, a6)

b2 :=a3

Просіванняелементів відбувається доти, поки весь вихідний масив не буде заповненийсимволами 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(l n).

Оскількиl = log2n, M2(n)=O(n log2 n)), C2(n)=O(nlog2 n), Але З(n) = C1(n) + C2(n), M(n) = M1(n)+ M2(n). Тому що C1(n) < C2(n), M1(n)< M2(n), остаточно одержуємо оцінки складності алгоритму TreeSortза часом:

M(n) = O(n log2n), 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];

/> <td/> />
Приклад:Нехай 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] < a[j] then begin

b := a[i]; a[i] := a[j]; a[j] := b

end

End;

Procedure Conflict(i, k: Integer);

Var j: Integer;

Begin

j := 2*i;

If j = k

then ConSwap(i, j)

else if j < k then begin

if a[j+1] > 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 i <= n div 2 then begin

SortTree(2*i); SortTree(2*i+1); Conflict(i, n)

end

end;

НаII-ом етапі — етапі просівання — для k від n до 2 повторюються наступні дії:

1.ПереставитиA[1] і A[k];

2.Побудуватисортуюче дерево початкового відрізка масиву A[1..k-1], усунувши конфлікт роду вкорені A[1]. Відзначимо, що 2-а дія вимагає введення в процедуру Conflictпараметра k.

Program HeapSort;

Const n = 100;

Var A: Array[1..n] of real;

k: Integer;

{процедури ConSwap, Conflict, SortTree, введення,виведення}

Begin

{ введення }

SortTree(1);

For k := n downto 2 do begin

ConSwap(k, 1); Conflict(1, k — 1)

end;

{ виведення }

End.

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

/>/>/> 1.3 Швидке сортування Хоара

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

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

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 перестановок. Теперзалишилося проробити ті ж дії з початком і кінцем масиву, тобто застосувати їхрекурсивно.

Такимчином, описана нами процедура 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 < R then begin

x := A[(L + R) div 2]; {вибір бар'єра x}

left := L; right := R ;

Repeat {зустрічний прохід}

While A[left] < x do Inc(left); {перегляд уперед}

While A[right] > x do Dec(right); {перегляд назад}

If left <= right then begin

Swap(left, right); {перестановка}

Inc(left); Dec(right);

end

until 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 log2n), M(n) = O(n log2 n)

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

/>/>1.4 Метод цифрового сортування

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

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

..........

n-1

...........

jn-1

у якому 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);

Vari,j:byte;

begin

if hi> lowthen

/>begin i:= low;

j:= hi;

x:= a[i];

/> While i< j do

if a[i+1]<=x then

begin

a[i]:= a[i+1];

a[i+1]:=x;

i:= i+1;

end

else

begin

if a[j]<=x then

begin

y:=a[j];

a[j]:=a[i+1];

a[i+1]:=y;

end;

j:=j-1

end;

-Qsort (a, low, i-1);

-Qsort (a, i+1, hi);

end;

ПроцедураMergesort виконуєсортування двох масивів “злиттям”. Тобто, спочатку перший масив сортується задопомогою процедури Qsort і другий масив сортується за допомогою цієї жпроцедури. Потім два, вже відсортованих масиви з’єднуються в один. А саме, задопомогою оператору “if” ми порівнюємо перший елемент одного і першийелемент другого масивів. Якщо один з них менший, то ми відсилаємо його в третіймасив, а індикатор пересуваємо на наступний елемент і знов порівнюємо їх. Зновуменший з двох елементів пересилаємо в третій масив, а індикатор пересуваємо.Також ми передбачили варіант, коли елементи, що порівнюються – однакові. Тоді втретій масив по-черзі записуються обидва елементи, а індикатори зміщуються нанаступні елементи в обох масивах. Якщо один з масивів виявився меншим закількістю елементів ніж інший, то решта елементів довшого масиву простопересилається до третього масиву в тій самій послідовності (адже вихідні масививже відсортовані раніше процедурою Qsort). Таким чином, врезультаті ми отримуємо третій масив з впорядкованими елементами.

Procedure Mergesort;

Var i, j, k: byte;

Begin

i:=1;

j:=1;

for k:=1 to n_c doc[k]:=0;

k:=1;

While ( i<= n_a )or ( j<=n_b ) do

if i= n_a+1then

begin

c[k]:=b[j];

k:=k+1;

j:= j+1;

end

else

if i= n_b+1then

begin

c[k]:=a[i];

k:= k+1;

i:=i+1 ;

end

else

if a[i]= b[j]then

begin

c[k]:=b[j];

c[k+1]:= a[i];

k:=k+2;

i:=i+1;

j:=j+1

end

else

if a[i] >b[j] then

begin

c[k]:= b[j];

k:= k+1;

j:= j+1;

end

else

begin

c[k]:= a[i];

k:=k+1;

i:= i+1;

end

End;

Третяпроцедура описує алгоритм швидкого сортування Хоара. Це є удосконалений методсортування, що базується на сортуванні обмінами. Тобто, спочатку ми обираємодеякий “бар’єр” (один з елементів масиву). Потім ми переглядаємо елементи, щостоять зліва від “бар’єра” і порівнюємо їх з ним. Коли ми знаходимо елемент,який є більшим за “бар’єр”, то ми починаємо перглядати масив з кінця,порівнюючи елементи з “бар’єром”. Якщо ми знайдемо в правій частині масивуелемент менший за “бар’єр”, то ми переставимо місцями елемент зліва (той, щобільше за “бар’єр”)і елемент з права ( той, що менше) і продовжимо перегляд. Потім ми рекурсивно застосовуємо цю процедуру для того, щоб відсортуватипочаток і кінець масиву. Реалізуємо цей алгоритм за допомогою циклів “While” та “Repeat Until” та оператору “if”, якийвідповідає за порівняння.

Procedure HoareSearch ( vara:mas; L, R: Integer);

Var left, right, b, x: Integer;

Begin

if L < R then

begin

x:= a[(L+R) div 2];

left:= L;

right:= R;

Repeat

While a[left] < x do left:= Succ(left);

Whilea[right] >x do right:= Pred(right);

Ifleft >= right then

Begin

b:= a[left];

a[left]:= a[right];

a[right]:=b;

left:=Succ( left);

right:= Pred(right);

End;

Until left >right;

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.

еще рефераты

Еще работы по информатике, программированию

Реферат по информатике, программированию

Відношення і схеми відношень

31 Августа 2013

Реферат по информатике, программированию

Ведение реляционной БД на яз. CLIPPER 5.02

18 Июня 2015

Реферат по информатике, программированию

Векторная графика

18 Июня 2015

Реферат по информатике, программированию

Взаимодействие основных частей ЭВМ при выполнении программы

31 Августа 2013