Лист оцінювання

з дисципліни «Алгоритми і структури даних»

на тему: «Створення навчаючої програми, яка використовує візуальне уявлення для алгоритму сортування масиву методом швидкого сортування (QuickSort)» студента 2 курсу 325a групи

Члени комісії_______ _______________

(підпис) (ініціали, прізвище)

_______ _______________

(підпис) (ініціали, прізвище)

_______ _______________

(підпис) (ініціали, прізвище)

Зміст

програмування алгоритм сортування швидкий

Вступ

1. Основні теоретичні аспекти алгоритму та сортування

1.1 Теоретичні відомості

1.2 Поняття алгоритму сортування

1.3 Класифікація параметрів оцінки алгоритмів

1.4 Характеристика методів сортування

2. Реалізація алгоритму «швидкого сортування»

2.1 Опис алгоритму «швидкого сортування»

2.2 Реалізація мовою програмування C#

3. Практичний розділ

4. Особливості реалізації програмного коду

5. Інструкція роботи з програмою

6. Результати іспитів

Висновок

Список використаних джерел

Вступ

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

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

В даній курсовій роботі будемо розглядати одне з кращих сортувань. Воно носить назву «швидке сортування», алгоритм якого визнаний найкращим.

Ціллю курсової роботи є вивчення сучасних технологій програмування та аналіз алгоритму «швидкого сортування».

Задачі курсової роботи:

1) вивчити теоретичну основу алгоритмів сортування;

2) розглянути алгоритм «швидкого сортування»;

3) реалізувати його мовою програмування;

4) провести аналіз роботи сортування.

1. Основні теоретичні аспекти алгоритму та сортування

1.1 Теоретичні відомості

Алгоритм - це точно визначена послідовність дій, яку необхідно зробити над даними для досягнення рішення задачі.

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

Алгоритм сортування - це алгоритм для впорядкування елементів у списку. У випадку, коли елемент списку має декілька полів, поле по котрому виконується сортування, називається ключем сортування. На практиці, у якості ключа є число, а в усіх інших полях зберігаються деякі дані, що ніяк не впливають на роботу алгоритму.

Практично кожен алгоритм сортування можна розбити на три частини:

1. Порівняння, що визначає впорядкованість пари елементів.

2. Перестановку, що змінює місцями пару елементів.

3. Алгоритм, що виконує порівняння та перестановку елементів до тих пір, поки всі елементи множини не будуть впорядкованими.

Ціллю алгоритмів сортування є впорядкування послідовності елементів даних.

1.2 Поняття алгоритму сортування.

Алгоритм (algorithm) - це будь-яка коректно визначена обчислювальна процедура, на вхід (input) якої подається деяка величина або набір величин, і результатом якої виявляється вихідна (output) величина або набір значень. Таким чином, алгоритм являє собою послідовність обчислювальних кроків, що перетворюють вхідні величини у вихідні.

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

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

Сортування являє собою процес упорядкування безлічі подібних інформаційних об'єктів у порядку зростання чи спадання їх значень. Наприклад, список A з n елементів буде відсортований у порядку зростання значень елементів, якщо A₁?A₂?…?A_n.

Ціль сортування - полегшити пошук елементів у відсортованій множені. У цьому сенсі елементи сортування присутні майже у всіх задачах. Впорядковані об'єкти містяться у телефонній книзі, у бібліотеках, словниках, майже усюди. Навіть маленьких дітей привчають приводити речі «у порядок», і вони стикаються із деяким видом сортування за довго до того, як пізнають дещо про арифметику.

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

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

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

1.3 Класифікація параметрів оцінки алгоритмів

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

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

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

Природність поведінки - ефективність методу при обробці вже відсортованих, або частково впорядкованих даних. Алгоритм поводиться природно, якщо враховує цю характеристику вхідної послідовності і працює краще.

Ще однією важливою властивістю алгоритму є його сфера застосування. Тут основних типів упорядкування два:

- Внутрішнє сортування оперує з масивами, цілком поміщається в оперативній пам'яті з довільним доступом до будь-якого осередку. Дані зазвичай упорядковуються на тому ж місці, без додаткових витрат.

- Зовнішнє сортування оперує з пристроями, що запам'ятовують, великого обсягу, але з доступом не довільним, а послідовним (впорядкування файлів), тобто в даний момент ми «бачимо» тільки один елемент, а витрати на перемотування в порівнянні з пам'яттю невиправдано великі. Це накладає деякі додаткові обмеження на алгоритм і призводить до спеціальних методів впорядкування, зазвичай використовують додатковий дисковий простір. Крім того, доступ до даних на носії виробляється набагато повільніше, ніж операції з оперативною пам'яттю.

В сучасних архітектурах персональних комп'ютерів широко застосовується підкачка і кешування пам'яті. Алгоритм сортування повинен добре поєднуватися з застосовуваними алгоритмами кешування і підкачки.

Доступ до носія здійснюється послідовним чином: в кожен момент часу можна зчитати або записати тільки елемент, наступний за поточним.

Обсяг даних не дозволяє їм розміститися в ОЗУ (оперативно запам'ятовуючий пристрій).

Також алгоритми класифікуються за:

- потреби в додатковій пам'яті або її відсутності;

- потреби в знаннях про структуру даних, що виходять за рамки операції порівняння, або відсутності такого.

Існує безліч методів сортування, кожен з яких має свої переваги і недоліки. Розглянемо лише деякі з них:

1) сортування бульбашкою;

2) сортування перемішуванням;

3) сортування методом вставок;

4) сортування підрахунком;

5) сортування злиттям;

6) цифрове сортування;

7) сортування методом вибору;

8) сортування методом Шелла;

9) обмінне сортування за розрядами;

10) пірамідальне сортування;

11) сортування масивом (змішування);

12) швидке сортування (метод хоара).

1.4 Характеристика методів сортування

1) Сортування бульбашкою.

Найбільш відоме є сортування бульбашкою. Його популярність пояснюється прикметною назвою і простотою алгоритму. Однак, це сортування є одним з найгірших серед усіх коли-небудь вигаданих сортувань. Метод дуже простий і полягає в наступному: береться пара елементів, що стоять поруч, і якщо елемент з меншим індексом виявляється більше елемента з більшим індексом, то ми міняємо їх місцями. Ці дії продовжуємо, поки є такі пари. Легко зрозуміти, що коли таких пар не залишиться, то дані будуть відсортованими. Для спрощення пошуку таких пар дані проглядаються від початку до кінця. З цього випливає, що за такого перегляду знаходиться максимум, який поміщається в кінець масиву, а тому наступного разу досить переглядати вже меншу кількість елементів. Максимальний мов спливає вгору, звідси і назва алгоритму. Так як кожен раз на своє місце стає, принаймні, один елемент, то не буде потрібно більше N проходів, де N - кількість елементів.

2) Сортування перемішуванням.

Являє собою різновид бульбашкового сортування. Відрізняється тим, що перегляди елементів виконуються один за іншим в протилежних напрямках, при цьому великі елементи прагнуть до кінця масиву, а маленькі до початку.

3) Сортування методом вставок.

Сортування методом вставок (англ. InsertionSort) - простий алгоритм сортування. Хоча цей метод сортування менш ефективний, ніж більш складні алгоритми (такі як швидке сортування), у нього є ряд переваг:

- простий в реалізації;

- ефективний на невеликих наборах даних;

- ефективний на наборах даних, які вже частково відсортовані;

- це стійкий алгоритм сортування (не змінює порядок елементів, які вже відсортовані);

- може сортувати список в міру його отримання.

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

4) Сортування підрахунком

Алгоритм сортування масиву, при якому підраховується число однакових елементів. Алгоритм вигідно застосовувати, коли в масиві багато елементів, але всі вони досить малі. Ідея сортування вказана в її назві - потрібно підраховувати число елементів, а потім вибудовувати масив. Нехай, наприклад, є масив A із мільйона натуральних чисел, менших 100. Тоді можна створити допоміжний масив B з 99 (1..99) елементів, «пробігти» весь вихідний масив і обчислювати частоту зустрічальності кожного елемента - тобто якщо A [i] = a, то B [a] слід збільшити на одиницю. Потім «пробігти» лічильником i масив B, записуючи в масив A число i B [i] раз.

5) Сортування злиттям

Сортування злиттям (англ. MergeSort) - алгоритм сортування, який впорядковує списки (або інші структури даних, доступ до елементів яких можна отримувати тільки послідовно, наприклад - потоки) в певному порядку. Алгоритм був винайдений Джоном фон Нейманом в 1945 році.

6) Цифрове сортування

Цифрове сортування (англ. PigeonholeSort) володіє лінійною обчислювальною складністю О (n), що є кращою можливою продуктивністю для алгоритму сортування, так як в будь-якому такому алгоритмі кожен сортований елемент необхідно переглянути хоча б один раз. Однак, застосування алгоритму цифрового сортування доцільно лише тоді, коли сортовані предмети мають (або їх можна відобразити) діапазон можливих значень, що досить малий у порівнянні з переліку, що сортується. Ефективність алгоритму падає щоразу, коли кілька різних елементів потрапляє в одну клітинку. Необхідність сортування всередині осередків позбавляє алгоритм сенсу, так як кожен елемент доведеться переглядати більш ніж один раз. Так що, для простоти і з метою відрізнити «класичне» цифрове сортування від його численних варіантів, вкажемо, що підрахунок повинен бути оборотним: якщо два елементи потрапляють в одну клітинку, то вони повинні мати однакове значення. Кілька елементів з одним значенням в одній комірці не псують картину - їх можна просто вставити в відсортований список поруч, один за іншим (це дозволяє застосовувати цифрове сортування в якості стійкого).

7) Сортування методом вибору.

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

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

8) Сортування методом Шелла.

Ідея алгоритму полягає в обміні елементів, розташованих не тільки поруч, як в сортуванні методом вставок, а й далеко один від одного, що значно скорочує загальне число операцій переміщення елементів

9) Обмінне сортування за розрядами.

Цей метод, зовсім відмінний від усіх схем сортування, які розглядалися раніше; в ньому використовується двійкове подання ключів, і тому він призначений виключно для довічних машин. Замість того щоб порівнювати між собою два ключа, в цьому методі перевіряється, чи рівні 0 або 1 окремі біти ключа. В інших відносинах він володіє характеристиками обмінного сортування і насправді дуже нагадує швидке сортування. Так як він залежить від розрядів ключа, представленого в двійковій системі числення, ми називаємо його "обмінним порозрядним сортуванням".

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

Пірамідальне сортування - алгоритм сортування, що працює в гіршому, в середньому і в кращому випадку (тобто гарантовано) за О (n log₂n) операцій при сортуванні n елементів.

Сортування пірамідою використовує сортувальне дерево. Сортувальне дерево - це таке бінарне дерево, у якого виконані умови:

- Кожен лист має глибину або d або d-1;

- Значення в будь-якій вершині більше, ніж значення її нащадків.

11) Сортування масивом (змішування).

Це найшвидший метод сортування, однак, існує безліч істотних недоліків.

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

12) Швидке сортування (метод Хоара).

Швидке сортування (англ. Quicksort) - широко відомий алгоритм сортування, розроблений англійським інформатики Чарльзом Хоаром. Дає в середньому O (nlog₂n) порівнянь при сортуванні n елементів. У гіршому випадку виходить O (n2) порівнянь. Зазвичай на практиці швидке сортування значно швидше, ніж інші алгоритми з оцінкою O (nlog₂n), по причині того, що внутрішній цикл алгоритму може бути ефективно реалізований майже на будь-якій архітектурі, і на більшості реальних даних можна знайти рішення, які мінімізують ймовірність того, що знадобиться квадратичне час.

2. Реалізація алгоритму «швидкого сортування»

У цьому розділі ми розглянемо сам алгоритм «швидкого сортування» та процедуру розбиття масиву на частини. Також реалізуємо його на мові програмування.

2.1 Опис алгоритму «швидкого сортування»

Швидке сортування, як і сортування злиттям, по своїй природі рекурсивне, тобто воно для рішення деякої задачі викликає себе для рішення її підзадач; і основана на принципі «розділяй та володарюй». Спочатку задача розбивається на декілька підзадач меншого розміру. Потім ці задачі вирішуються. І нарешті, їх рішення комбінуються та виходить рішення вихідної задачі.

Сортування ділянки А [p..r] відбувається так:

· Елементи масиву А переставляються так, щоб будь-який з елементів А[р]…А[q] був не більше будь-якого з елементів А [q+1]…A[r], де q - деяке число на інтервалі p?q<r. Цю операцію ми будемо називати поділом (part).

· Процедура сортування рекурсивно викликається для масивів A[p..q] та A[q+l..r].

Після цього масив A[p…r] відсортований.

Отже, процедура сортування QuickSort виглядає наступним чином:

Quicksort (p, r)

1) якщо p<r;

2) то q<part (p, r);

3) Quicksort (p, q);

4) Quicksort ( q+ 1, r).

Ключовою частиною розглянутого алгоритму сортування є функція part, що змінює порядок елементів масиву А [р..r] без залучення додаткової пам'яті.

Вибираємо елемент x = А [р] в якості «граничного»; масив А [р..q] буде містити елементи, не більші за х. А масив A [q + l..r] - елементи, не менші х. Ідея полягає в тому, щоб накопичувати елементи, не більші за х, в початковому відрізку масиву A [p..i], а елементи, не менші за х - в кінці A [j..r]. На початку обидва «накопичувача» порожні: i = р-1, j = r + 1:

i < p-1;

j <r+1;

x <A[p];

Створимо цикл, в якому знайдемо елементи A [j] ? x і A [i] ? x. Для цього ми будемо зменшувати j, поки A [j] ? x та збільшувати i, поки A [i] ? x. Потім, порівнюючи i та j, подивися, де знаходяться наші елементи в масиві A [p..i] або в масиві A [j..r]. Потім перевіримо чи виконується нерівність i <j, якщо так, то ми поміняємо місцями A [i] та A [j], якщо ж ні, то функції присвоюємо значення j.

Хоча ідея функції дуже проста, сам алгоритм містить ряд тонких моментів. Наприклад, не очевидно, що індекси i та j не виходять за межі проміжку [р..r] в процесі роботи. Інший приклад: важливо, що в якості граничного значення вибирається А [р], а не, скажімо, A [r]. В останньому випадку може виявитися, що A [r] - найбільший елемент масиву, і в кінці виконання процедури буде i = j = r, так що повертати j функції буде не можна - порушиться вимога q <r, і процедура QuickSort зациклиться.

Час роботи функції part становить , де .

2.2 Реалізація мовою програмування C#

Ми розглянули алгоритм «швидкого сортування», який описали звичайною мовою, зрозумілою майже всім. А для реалізації даного алгоритму була вибрана мова програмування C#.

Розглянемо базові процедури і функції, які використовувалися при написанні програми.

Для швидкого сортування нам знадобиться функція QuickSort, що приймає у якості параметрів лівий лемент масиву left, правий елемент масиву right та сам масив, що ми задали input.

У нашій функції корінь, відносно якого ми будемо порівнювати елементи, pivot, ліва границя масиву - l_hold, права границя масиву - r_hold. Для початку ми прирівняли лівий елемент масиву до кореня.

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

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

Надалі ми зсуваємо ліву границю, доки лівий елемент менший за корінь.

Наступний цикл буде за умови, що границі не зімкнулися. Ми переміщуємо корінь на місце правого елемента. Палички ще раз змінюють своє положення та зсуваємо праву границю вправо. Виходимо з циклу.

Друкуємо наш масив. Виходимо з циклу.

Далі ставимо корінь на місце лівого елементу. Наступним кроком ставимо корінь у ліву границю, а правий елемент - у праву границю. Рекурсивно викликаємо сортування для лівої та правої частини.

Після закінчення роботи функції отримуємо відсортований масив.

Псевдокод функції швидкого сортування:

while (left < right)

{

while ((input[right] >= pivot) && (left < right))

right--;

if (left != right)

{

input[left] = input[right];

SwapLines(left, right);

left++;

}

while ((input[left] <= pivot) && (left < right))

left++;

if (left != right)

{

input[right] = input[left];

SwapLines(right, left);

right--;

}

PrintArray(ArrayNumbers);

}

input[left] = pivot;

pivot = left;

left = l_hold;

right = r_hold;

if (left < pivot)

QuickSort(input, left, pivot - 1);

if (right > pivot)

QuickSort(input, pivot + 1, right);

return input;

3. Практичний розділ

У якості прикладу розглянемо масив A =[10, 4, 2, 14, 67, 2, 11, 33, 1, 15], кількість елементів якого n=10. Коренем стане лівий елемент 10, лівий елемент - 4, правий - 15.

Покажчик лівого елементу переміщується до тих пір, поки не знайде елемент, що більший за 10; правий рухається, поки не знайде елемент, що менший за 10.

Ці елементи обмінюються місцями та рух покажчиків поновлюється.

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

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

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

4. Особливості реалізації програмного коду

Написання програмного коду було здійснене у середовищі розробки VisualStudio за допомогою мови програмування С#. Для реалізації інтерфейсу було використано платформу інтерфейсу WPF (Windows Presentation Foundation).

Для реалізації інтерфейсу та сортування даних у програмі використовується один файл - MainWindow.xaml.cs, у якому містяться:

1) MainWindow - конструктор головної форми.

2) InitializeLines - побудова ліній на форму.

3) EndProgram - обробка закриття програми.

4) RunSorting - виклик функції сортування.

5) QuickSort - сама функція сортування.

6) SetColor - зміна кольору палички, котрі на своєму місці.

7) SwapLines - зміна положення двох паличок.

8) InitializeRandom - ініціалізація паличок та значень.

9) PrintArray - печать масиву значень.

10) OpenBtn_Click - зчитування з файлу.

11) SaveBtn_Click -збереження результату у файл.

5. Інструкція роботи з програмою

Наша програма реалізує алгоритм швидкого сортування. Вхідні дані - масив з цілих чисел. Він може бути зчитаний з файлу у формату «.txt» або може бути заданий рандомно. У файлі елементи повинен розділяти пробіл.

Рисунок 1 Вхідні дані, коректно записані у файл

Для того, щоб працювати з масивом, який записаний у файл, у вікні програми (рисунок 2) натискаємо на кнопку «open from file». З'являється вікно, у якому ми повинні обрати наш текстовий файл з коректно записаними вхідними даними (рисунок 3). Дані будуть відображені у вікні програми (рисунок 4). Ще один спосіб задання даного масиву - генерація його за допомогою функції рандому. Для цього потрібно у вікні програми (рисунок 2) натиснути на кнопку «Random». Дані будуть відображені у вікні програми (рисунок 5).

Якщо дані введено невірно, то з'явиться вікно помилки (рисунок 6).

Рисунок 2 Вікно програми

Рисунок 3 Вибір файлу

Рисунок 4 Коректно відображені дані

Рисунок 5 Рандомізація масиву

Рисунок 6 Вікно помилки

Для початку роботи програми потрібно натиснути кнопку «Sort». На екрані палички почнуть змінювати своє позицію. По завершенню роботи сортування масиву палички будуть розташовані у порядку зростання (рисунок 7, 9) та з'явиться вікно, що покаже на час роботи функції сортування (рисунок 8, 10).

Рисунок 7 Завершення роботи сортування (для рандомного масиву)

Рисунок 8 Час, за який працює функція сортування (для рандомного масиву)

Рисунок 9 Завершення роботи сортування (для масиву з файлу)

Рисунок 10 Час, за який працює функція сортування (для масиву з файлу)

Додатково можна ще змінити колір паличок, що сортуються. Це можна зробити, натиснувши на кнопку під написом «Gradient Color» (рисунок 11). Є три види кольору: червоний (Red), (рисунок 12), зелений (Green), (рисунок 13) та синій (Blue), (рисунок 14).

Рисунок 11 Вибір кольору паличок

Рисунок 12 Червоний колір паличок

Рисунок 13 Зелений колір паличок

Рисунок 14 Синій колір паличок

За допомогою повзунків Elements та Delay(ms) можна змінювати кількість елементів (від 15 до 40) та затримку кадрів (від 100 до 500).

6. Результати іспитів

Для перевірки складності алгоритму програми було проведено 6 тестів на наборах даних з 15, 20, 25, 30, 35, 40 елементів. Були отримані такі результати:

Таблиця 1

Результати тестування

За результатами тестування був побудований графік залежності часу сортування від розмірності масиву (рисунок 15).

Рисунок 15 Графік залежності

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

Висновок

Для вирішення задачі сортування масиву у курсовому проекті було поставлено та виконано декілька цілей. Була вивчена предметна область задачі, розглянуті теоретичні відомості. Основне завдання - написання програми з графічним інтерфейсом сортування масиву - виконане.

Було проведено тестування алгоритму для порівняння наших результатів із теоретичними даними.

Можна зробити висновок про те, що розглянутий алгоритм має і переваги, і недоліки. Переваги швидкого сортування:

- одне з найшвидших сортувань (на практиці);

- простий у реалізації;

- потребує мало додаткової пам'яті для своєї роботи;

- добре поєднується з механізмами кешування та віртуальної пам'яті;

- існує ефективна модифікація (алгоритм Седжвіка) для сортування строк: спочатку порівняння з ключем тільки по нульовому символу строки, далі використання аналогічного сортування для «більшого» та «меншого» масивів також по нульовому символу, та для «рівного» масиву по вже першому символу;

- працює на зв'язних списках та інших структурах з послідовним доступом.

Недоліки швидкого сортування:

- нестійкий. Якщо потрібна стійкість, доводиться розширювати ключ;

- погана реалізація може призвести до помилки переповнення стеку;

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

Список використаних джерел

1. Ткачук В. Все про програмування [Електронний ресурс]. Режим доступу: http://www.ru-coding.com/algoritm_1.php.

2. Ткачук В. Алгоритми сортування [Електронний ресурс]. Режим доступу: http://base.vingrad.ru/view/130-Algoritmyi-sortirovki

3. Роберт Седжвік. Фундаментальні алгоритми на С++. Частини 1-4: Аналіз/Структури даних/Сортування/Пошук

4. Вірт Н. Алгоритми и структури даних; М., 2008. 537 c.

5. Дональд Э. Кнут Мистецтво програмування. Том 3. Сортування та пошук; Вільямс - М., 2012. 824 c.

6. Кнут Д.Э. Мистецтво програмування (Том 1. Основні алгоритми); М., 2000. 879 c.

Додаток А

Файл MainWindow.xaml.cs

using System;

using System.Windows.Shapes;

using System.Windows;

using System.Windows.Media;

using System.Threading;

using System.Windows.Threading;

using System.Windows.Controls;

using System.IO;

using Microsoft.Win32;

using System.Diagnostics;

namespace QuickSort

{

public partial class MainWindow: Window

{

// задержка

private int RealDeley = 100;

//отступы

private double Xcord = 10, Ycord = 230;

//массив значений

private int[] ArrayNumbers;

//массив линий

private Line[] ArrayLines;

private Thread ThreadSort;

public MainWindow()//конструктор главной формы

{

InitializeComponent();

Closed += EndProgram;//добавление в стандартный делегат класса событие выключения программы

InitializeRandom();

}

private void InitializeLines(int[] array)

{

//построение линий на форму

DrawingCanvas.Children.Clear();

ArrayLines = new Line[array.Length];

for (int i = 0; i < array.Length; i++)

{//чоздает линию по заданым координатам

Line OneLine = new Line();

OneLine.X1 = Xcord + (double)(i + 1) * 30;

OneLine.Y1 = Ycord;

OneLine.X2 = OneLine.X1;

OneLine.Y2 = -1 * array[i] + OneLine.Y1;

OneLine.StrokeThickness = 20;

SolidColorBrush brush = null;

switch (SelectColor.SelectedIndex)//выбор цвета для линий

{

case 0:

{

brush = new SolidColorBrush(Color.FromArgb(250, (byte)(array[i] + 70), 0, 0));

break;

}

case 1:

{

brush = new SolidColorBrush(Color.FromArgb(250, 0, (byte)(array[i] + 70), 0));

break;

}

case 2:

{

brush = new SolidColorBrush(Color.FromArgb(250, 0, 0, (byte)(array[i] + 70)));

break;

}

default:

break;

}

OneLine.Stroke = brush;

ArrayLines[i] = OneLine;

//отрисивока линий на форму

DrawingCanvas.Children.Add(OneLine);

}

//основная линия(полотнро)

Line MainLine = new Line();

MainLine.X1 = Xcord;

MainLine.Y1 = Ycord + 15;

MainLine.X2 = Xcord;

MainLine.Y2 = Ycord;

MainLine.StrokeThickness = array.Length * 65;

MainLine.Stroke = Brushes.Gray;

DrawingCanvas.Children.Add(MainLine);

}

private void EndProgram(object sender, EventArgs e)

{

//обработка закрытия программы

if (ThreadSort != null)

ThreadSort.Abort();//остановка потока

Close();

}

private void RunSorting()

{

//вызов сортировки и отлючение кнопок

RunButton.IsEnabled = false;

RandomButton.IsEnabled = false;

InputN.IsEnabled = false;

InputDelay.IsEnabled = false;

OpenBtn.IsEnabled = false;

SaveBtn.IsEnabled = false;

SelectColor.IsEnabled = false;

int selectColor = SelectColor.SelectedIndex;

ThreadSort = new Thread(delegate()

{

//запуск сортировки, по окончанию включение кнопок, запуск потока для отрисовки

//подсчет времени работы сортировки

Stopwatch stopWatch = new Stopwatch();//экземпляр класса для подсчета времени

stopWatch.Start();

ArrayNumbers = QuickSort(ArrayNumbers, 0, ArrayNumbers.Length - 1);//запуск сортировки

Dispatcher.BeginInvoke(DispatcherPriority.Normal, (ThreadStart)delegate()//окно для второго потока (чтобы в первом потоке включить кнопки по окончанию работы сортировки)

{

RunButton.IsEnabled = false;

RandomButton.IsEnabled = true;

InputN.IsEnabled = true;

InputDelay.IsEnabled = true;

OpenBtn.IsEnabled = true;

SaveBtn.IsEnabled = true;

SelectColor.IsEnabled = true;

stopWatch.Stop();//остановка времени

TimeSpan ts = stopWatch.Elapsed;//подсчет времени

string elapsedTime = String.Format("{0:00}:{1:00}:{2:00}.{3:00}", ts.Hours, ts.Minutes, ts.Seconds, ts.Milliseconds / 10);//вывод времени

MessageBox.Show(elapsedTime, "Время работы");

});

});

ThreadSort.Start();//остановка потока

}

// Функция быстрой сортировки

private int[] QuickSort(int[] input, int left, int right)

{

int pivot; // разрешающий элемент

int l_hold = left; //левая граница

int r_hold = right; // правая граница

pivot = input[left];//разрешающий элемент - левая граница

while (left < right) // пока границы не сомкнутся

{

while ((input[right] >= pivot) && (left < right))

right--; // сдвигаем правую границу пока элемент [right] больше [pivot]

if (left != right) // если границы не сомкнулись

{

Thread.Sleep(RealDeley); //задержка

input[left] = input[right]; // перемещаем элемент [right] на место разрешающего

SwapLines(left, right); //изменение положения палочек

left++; // сдвигаем левую границу вправо

}

while ((input[left] <= pivot) && (left < right))

left++; // сдвигаем левую границу пока элемент [left] меньше [pivot]

if (left != right) // если границы не сомкнулись

{

Thread.Sleep(RealDeley); //задержка

input[right] = input[left]; // перемещаем элемент [left] на место [right]

SwapLines(right, left); //изменение положения палочек

right--; // сдвигаем правую границу вправо

}

PrintArray(ArrayNumbers); //печать массива

}

input[left] = pivot; // ставим разрешающий элемент на место

pivot = left;

left = l_hold;

right = r_hold;

if (left < pivot) // Рекурсивно вызываем сортировку для левой и правой части массива

QuickSort(input, left, pivot - 1);

if (right > pivot)

QuickSort(input, pivot + 1, right);

return input;

}

private void SetColor(int index, int gr, int selectColor)

{

//изменение цвета палочки, которые на своём месте

gr += 80;

Dispatcher.BeginInvoke(DispatcherPriority.Normal, (ThreadStart)delegate()

{

SolidColorBrush brush = null;

switch (selectColor)//выбор цвета палочки

{

case 0:

{

brush = new SolidColorBrush(Color.FromArgb(250, (byte)gr, 0, 0));

break;

}

case 1:

{

brush = new SolidColorBrush(Color.FromArgb(250, 0, (byte)gr, 0));

break;

}

case 2:

{

brush = new SolidColorBrush(Color.FromArgb(250, 0, 0, (byte)gr));

break;

}

default:

break;

}

ArrayLines[index].Stroke = brush;

});

}

private void SwapLines(int index1, int index2)

{

//изменение положения двух палочек

Dispatcher.BeginInvoke(DispatcherPriority.Normal, (ThreadStart)delegate()//расчетт координат палочки при изменении её положения

{

double FirstX = ArrayLines[index1].X1;

double FirstY = ArrayLines[index1].Y1;

double SecondX = ArrayLines[index2].X1;

double SecondY = ArrayLines[index2].Y1;

ArrayLines[index2].X1 = FirstX;

ArrayLines[index2].Y1 = FirstY;

ArrayLines[index2].X2 = ArrayLines[index2].X1;

ArrayLines[index2].Y2 = -1 * ArrayNumbers[index2] + ArrayLines[index2].Y1;

ArrayLines[index1].X1 = SecondX;

ArrayLines[index1].Y1 = SecondY;

ArrayLines[index1].X2 = ArrayLines[index1].X1;

ArrayLines[index1].Y2 = -1 * ArrayNumbers[index1] + ArrayLines[index1].Y1;

});

//изменение положений палочек

Line temp = ArrayLines[index1];

ArrayLines[index1] = ArrayLines[index2];

ArrayLines[index2] = temp;

}

private void InitializeRandom()

{

//инициализация палочек и значений

RealDeley = (int)InputDelay.Value;//заполнение массива рандомными значениями

Random random = new Random();

ArrayNumbers = new int[(int)InputN.Value];

for (int i = 0; i < (int)InputN.Value; i++)

ArrayNumbers[i] = random.Next(30, 170);

InitializeLines(ArrayNumbers);//вывод линий на экран по значению массива

OutputTextBox.Children.Clear();

foreach(int i in ArrayNumbers)//создание меток с цифрой из массива

//вывод на экран

{

Grid g = new Grid();

Ellipse el = new Ellipse();

el.Width = 50;

el.Height = 50;

el.VerticalAlignment = VerticalAlignment.Top;

el.Fill = Brushes.Blue;

el.Stroke = Brushes.Red;

el.StrokeThickness = 3;

g.Children.Add(el);

Label label = new Label();

label.FontSize = 25;

label.Content = i;

label.BorderThickness = new Thickness(4);

g.Children.Add(label);

OutputTextBox.Children.Add(g);

}

RunButton.IsEnabled = true;

}

private void RandomButton_Click(object sender, RoutedEventArgs e)

{

InitializeRandom();

}

private void InputN_ValueChanged(object sender, RoutedPropertyChangedEventArgs<double> e)

{

Quantity.Content = ((int)InputN.Value).ToString();

}

private void InputDelay_ValueChanged(object sender, RoutedPropertyChangedEventArgs<double> e)

{

Delay.Content = ((int)InputDelay.Value).ToString();

}

private void PrintArray(int[] array)

{

//печать массива значений

Dispatcher.BeginInvoke(DispatcherPriority.Normal, (ThreadStart)delegate()

{

OutputTextBox.Children.Clear();

foreach(int i in array)

{

Grid g = new Grid();

Ellipse el = new Ellipse();

el.Width = 50;

el.Height = 50;

el.VerticalAlignment = VerticalAlignment.Top;

el.Fill = Brushes.Blue;

el.Stroke = Brushes.Red;

el.StrokeThickness = 3;

g.Children.Add(el);

Label label = new Label();

label.FontSize = 25;

label.Content = i;

label.BorderThickness = new Thickness(4);

g.Children.Add(label);

OutputTextBox.Children.Add(g);

}

});

}

private void OpenBtn_Click(object sender, RoutedEventArgs e)

{

//Считывание с файла

try

{

OpenFileDialog openFileDialog = new OpenFileDialog();

openFileDialog.Filter = "Text documents (.txt)|*.txt";

openFileDialog.ShowDialog();

string temp = File.ReadAllText(openFileDialog.FileName);

string[] Lines = temp.Split(new char[] { ' ' }, StringSplitOptions.RemoveEmptyEntries);

if (Lines.Length > InputN.Maximum || Lines.Length < InputN.Minimum)

throw new Exception("Ошибка");

ArrayNumbers = new int[Lines.Length];

for (int i = 0; i < Lines.Length; i++)

ArrayNumbers[i] = Int32.Parse(Lines[i]);

InitializeLines(ArrayNumbers);

OutputTextBox.Children.Clear();

foreach(int i in ArrayNumbers)

{

Label label = new Label();

label.Background = Brushes.Wheat;

label.FontSize = 30;

label.Content = i;

label.BorderThickness = new Thickness(4);

OutputTextBox.Children.Add(label);

}

RunButton.IsEnabled = true;

}

catch (Exception exce)

{

MessageBox.Show(exce.Message);

}

}

private void SaveBtn_Click(object sender, RoutedEventArgs e)

{

try

{

//сохранение результата в файл

SaveFileDialog saveFileDialog = new SaveFileDialog();

saveFileDialog.Filter = "Text documents (.txt)|*.txt";

saveFileDialog.ShowDialog();

string SaveResult = "";

for (int i = 0; i < ArrayNumbers.Length; i++)

SaveResult += ArrayNumbers[i].ToString() + " ";

File.WriteAllText(saveFileDialog.FileName, SaveResult);

MessageBox.Show("Файл сохранён", "Система");

}

catch (Exception exce)

{

MessageBox.Show(exce.Message);

}

}

private void RunSortingButton_Click(object sender, RoutedEventArgs e)

{

RunSorting();

}

}

}

Размещено на Allbest.ru