Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Порівняння методів сортування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
РТ
Кафедра:
Кафедра програмного забезпечення
Інформація про роботу
Рік:
2015
Тип роботи:
Звіт про виконання лабораторної роботи
Предмет:
Алгоритми і структури даних
Група:
ПІ
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Інститут комп’ютерних наук та інформаційних технологій
Кафедра програмного забезпечення
/
ЗВІТ
Про виконання лабораторної роботи №7
«Порівняння методів сортування»
з дисципліни «Алгоритми і структури даних»
Лектор:
доц. кафедри ПЗ
Коротєєва Т.О.
ТЕМА: Порівняння методів сортування.
МЕТА: Порівняти вивчені раніше алгоритми сортування. Побудувати таблицю і графік швидкодії таких алгоритмів сортування. Зробити висновки щодо застосовності цих алгоритмів.
КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Алгоритм, алгорифм (латинізоване «Algorithmi», від імені узбецького математика IX століття аль-Хорезмі) — система правил виконання обчислювального процесу, що обов’язково приводить до розв’язання певного класу задач після скінченного числа операцій. При написанні комп’ютерних програм алгоритм описує логічну послідовність операцій. Поняття алгоритму належить до первісних понять математики. Обчислювальні процеси алгоритмічного характеру (арифметичні дії над цілими числами, знаходження найбільшого спільного дільника двох чисел тощо) відомі людству з глибокої давнини. Проте в явному вигляді поняття алгоритму сформувалося лише на початку XX століття.
Термін сортування (англійською «Sorting») означає розділення елементів за певними ознаками (сортами) і не дуже точно описує поставлену задачу. Більш точним була б назва впорядкування (англійською «Ordering»), але через перевантаженість слова «порядок» (англійською «Order») різними значеннями, в цьому контексті ним не скористалися.
Алгоритм сортування — це алгоритм, що розв'язує задачу сортування, тобто здійснює впорядкування лінійного списку (масиву) елементів.
На практиці елементи, що впорядковуються, рідко бувають просто числами. Набагато частіше, кожен такий елемент є записом (англійською «Record»). В кожному записі є ключ (англійською «Key»), по якому власне і здійснюється впорядкування, в той же час є й інша супутня інформація. Алгоритм сортування на практиці має бути реалізований так, щоб разом з ключами переміщати і супутню інформацію. Якщо кожен запис містить супутню інформацію великого об’єму, то з метою звести до мінімуму переписування великих об’ємів інформації, впорядкування відбувається не у самому масиві елементів, а в масиві вказівників на елементи.
Сам метод сортування не залежить від того, чи впорядковуються тільки числа, чи також і супутня інформація, тому при описі алгоритмів для простоти припускають, що елементи є числами.
Для алгоритму сортування (як і для будь-якого іншого сучасного алгоритму) основними характеристиками є обчислювальна та ємнісна складність. Крім цих двох характеристик, сортування поділяють на стабільні та нестабільні, з використанням додаткової інформації про елементи, чи без використання.
Стабільним (англійською «Stable») називається такий алгоритм сортування, що не змінює порядок елементів з однаковим ключем.
Для значної кількості алгоритмів середній і найгірший час впорядкування масиву з n елементів є O(n2), це пов’язано з тим, що в них передбачені перестановки елементів, що стоять поряд (різниця між індексами елементів не перевищує деякого заданого числа). Такі алгоритми зазвичай є стабільними, хоча і не ефективними для великих масивів.
Інший клас алгоритмів здійснює впорядкування за час O(n∙log(n)). В цих алгоритмах використовується можливість обміну елементів, що знаходяться на будь-якій відстані один від одного.
Теорема про найкращий час сортування стверджує, що якщо алгоритм сортування в своїй роботі спирається тільки на операції порівняння двох об’єктів (≤) і не враховує жодної додаткової інформації про елементи, то він не може впорядкувати масив елементів швидше ніж за O(n∙log(n)) в найгіршому випадку.
Довести цю теорему нескладно. На кожному кроці алгоритм проводить одне порівняння, результатом якого є один з двох варіантів:
1. A ≤ B.
2. A > B.
В залежності від результату порівняння алгоритм буде виконувати подальші дії. Значить, всю роботу алгоритму можна представити у вигляді бінарного дерева в листах якого лежать можливі перестановки вхідного масиву.
Отже, дерево має n! листів, значить висота дерева дорівнює log(n!). Час роботи в найгіршому випадку пропорційний висоті дерева:O(log(n!)) = O(log((2πn)½∙(n/e)n)) = O(n∙log(n)).
Такі швидкі алгоритми використовуються в реальних задачах. Проте більшість з них нестабільні. Стабільні алгоритми, що працюють за час O(n∙log(n)) потребують E(n) додаткової пам’яті.
Відомий стабільний алгоритм сортування, що не вимагає додаткової пам’яті працює за час O(n∙log2n).
Ще один клас алгоритмів використовує в своїй роботі деяку додаткову інформацію про елементи, що впорятковуються (наприклад, те що вони є різними числами в деякому діапазоні). Завдяки цьому, вони працюють за час O(n).
ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
1. Відвідати лекцію, вислухати та зрозуміти пояснення лектора. Прочитати та зрозуміти методичні вказівки, рекомендовані джерела та будь-які інші матеріали, що можуть допомогти при виконанні лабораторної роботи. Відвідати лабораторне заняття, вислухати та зрозуміти рекомендації викладача.
2. Скомпілювати всі шість раніше написаних програм .
3. Запустити на виконання кожну з написаних раніше програм щонайменше сім разів, отримати таким чином значення часу сортування масивів щонайменше семи різних розмірів з кожним з шести вивчених методів. В якості набору значень розмірів масивів можна використати, наприклад, таку послідовність чисел:
1) 1024;
2) 4096;
3) 16384;
4) 65536;
5) 262144;
6) 1048576;
7) 4194304 (в разі якщо сортування відбувається довше, ніж 5 хвилин — переривати роботу програми та вважати час сортування нескінченно великим).
ТЕКСТ ПРОГРАМИ
void createGrid()
{
Form1->TimeGrid->Cells[0][1] = "T(ns)";
Form1->TimeGrid->Cells[0][0] = "Sorting";
Form1->TimeGrid->Cells[1][0] = "Bubble";
Form1->TimeGrid->Cells[2][0] = "Selection";
Form1->TimeGrid->Cells[3][0] = "Shell";
Form1->TimeGrid->Cells[4][0] = "Merge";
Form1->TimeGrid->Cells[5][0] = "Quick";
Form1->TimeGrid->Cells[6][0] = "Counting";
}
void __fastcall TForm1::callChartBtnClick(TObject *Sender)
{
TimeGrid->Visible = true;
TimeChart->Visible = true;
TimeLabel->Visible = false;
createGrid();
Series1->Clear();
int length = Form1->NumberEdit->Text.ToInt();
double *array = new double[length];
initArray(array,length);
double*p = array;
//bubbleSort(p,length);
//std::sort(array,array+length,wayToSort);
p = array;
//selection(p,length);
p = array;
sort_shell(p,length);
p = array;
mergeNTime(p,length);
p = array;
countSort(p,length);
p = array;
//quickNTime(p,length);
delete[]array;
}
//---------------------------------------------------------------------------
РЕЗУЛЬТАТИ
/
Рис.1 Графік і таблиця значень часу сортувань для різних методів з розмірністю масиву 1024
/
Рис.2 Графік і таблиця значень часу сортувань для різних методів з розмірністю масиву 4096
/
Рис.3 Графік і таблиця значень часу сортувань для різних методів з розмірністю масиву 16384
/
Рис.4 Графік і таблиця значень часу сортувань для різних методів з розмірністю масиву 65536
/
Рис.5 Графік і таблиця значень часу сортувань для різних методів з розмірністю масиву 262144 (з врахуванням того, що час сортування вибіркою та бульбашкою та швидким є нескінченно великим)
/
Рис.6 Графік і таблиця значень часу сортувань для різних методів з розмірністю масиву 1048576 (з врахуванням того, що час сортування вибіркою,бульбашкою, злиттям та швидким методом є нескінченно великим)
/
Рис. 7 Графік і таблиця значень часу сортувань для різних методів з розмірністю масиву 4194304 (з врахуванням того, що час сортування вибіркою,бульбашкою та швидким методом є нескінченно великим)
ВИСНОВОК
На цій лабораторній роботі, я порівняв швидкість роботи, вивчених раніше алгоритмів сортування, побудував графік і таблицю їх швидкодії.
18.12.2015 00:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора