Аналіз алгоритму сортування методом вставки. Лабораторна робота з Теорія алгоритмів. Робота № 530480

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

Інформація про навчальний заклад

ВУЗ:

Вінницькій національний технічний університет

Інститут:

Не вказано

Факультет:

інформаційних технологій та комп ютерної інженерії

Кафедра:

Не вказано

Інформація про роботу

Рік:

2018

Тип роботи:

Лабораторна робота

Предмет:

Теорія алгоритмів

Завантажити

Частина тексту файла (без зображень, графіків і формул):

Міністерство освіти і науки України Вінницький національний технічний університет Факультет інфотмаційних технологій та комп’ної інженерії Кафедра комп’ютерних наук Лабораторна робота №1 З дисципліни «Теорія Алгоритмів» Тема: «Аналіз алгоритму сортування методом вставки» Тема: Аналіз алгоритму сортування методом вставки. Мета: навчитись аналізувати алгоритми на прикладі алгоритму сортування методом вставки Хід роботи Дослідження методу сортування вставками. Сортування вставками – алгоритм сортування в якому елементи вхідної послідовності переглядаються по одному і кожен наступний елемент розміщується в підходяще місце серед раніше упорядкованих елементів. Сортування вставками - простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як: швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг: -простота у реалізації; -ефективний (за звичай) на маленьких масивах; -ефективний при сортуванні масивів, дані в яких вже непогано відсортовані; Ідея методу сортування вставками досить проста. Цей метод часто використовують при сортуванні карток: беремо один елемент і вставляємо його в потрібне місце серед тих, що ми вже обробили (тим самим залишаючи їх відсортованими), при цьому більший елемент і всі елементи що знаходяться після нього зсуваються на 1 позицію вправо. Схема алгоритму, псевдокод, приклад дослідження. 02.1 Схема алгоритму: 2.2 Псевдокод: for j = 2 to A, length key = A [ j ] i = j - 1 While i > 0 and A [ i ] > key A [ i + 1 ] = A [ i ] i = i – 1 A [ i + 1 ] = key 2.3 Приклад дослідження: Нехай дано одномірний масив з такими елементами: 5, 1, 3, 4, 2. То згідно схеми алгоритму, зазначеної вище сортування буде відбуватися так: Створення програми, що сортирує масив методом вставки: Random zap = new Random(); Console.WriteLine("введіть кількість елементів масиву:"); int a = Convert.ToInt32(Console.ReadLine()); int[] arr1 = new int[a]; Console.WriteLine("початковий масив:"); //-Створення масиву for (int i = 0; i < a; i++) { arr1[i] = zap.Next(1, 100); Console.Write(arr1[i] + " "); } //////////// Сортування масиву в порядку зростання //////////// Stopwatch watch = new Stopwatch(); // -Cтворення таймера; watch.Start(); // -Запуск таймера; for (int j = 1; j < arr1.Length; j++) // -Cтворюємо лічильник зі змінною j, яка дор. // ідентифікатору наступного елемента массива; { int key = arr1[j]; // -Вводимо змінну key яка буде перевіряти чи // більше попереднє число наступного; int i = j - 1; // -Вводимо змінну і, яка дор. ідентефікатору // попереднього елемента массива; while (i >= 0 && arr1[i] > key) // -Перевіряємо умову чи змінна і більша або // дор. 0 та чи попередній елемент массиву // більший за змінну key; { // arr1[i + 1] = arr1[i]; // -Елемент стає на своє місце в відсортованій i = i - 1; } // частині массиву; arr1[i + 1] = key; } watch.Stop(); // -Зупинка таймера; Console.WriteLine("\nВідсортований по зростанню масив:"); for (int i = 0; i < arr1.Length; i++) { Console.Write(arr1[i] +" "); } Console.WriteLine("\Час виконання програми в мілісекундах : " +watch.ElapsedMilliseconds + "mc.\r\n"+ "\Час виконання програми в секундах : " + watch.Elapsed.Seconds + "сек.\r\n"); Дослідження часу виконання алгоритму сортування вставками залежно від кількості вхідних даних: КІЛЬКІСТЬ ЕЛЕМЕНТІВ Час сортування відсортованого масиву Час сортування невідсортованого масиву Час сортування в зворотному порядку 1000 елементів 1мс 5,67 с 86,34 с 5000 елементів 29мс 23,15 с 286,92 с 10000 елементів 313мс 35,43 с 423,34 с 50000 елементів 2843мс, 2 с 80,23 с 921,44 с 100000 елементів 11251мс, 11 с 143,67 с 2145,75 с Для невідсортованого масиву Для відсортованого по спаданню масиву На виході ми отримуємо параболічну залежність часу від кількості вхідних даних. Ми можемо теоретично розрахувати час виконання алгоритму за формулами: (Для кращого випадку) (Для гіршого випадку) Якщо порівняти результати на практиці з теоретичними розрахунками часу виконання алгоритму в найгіршому і найкращому випадку, то можемо побачити що параболічна залежність зберігається. Висновок: під час виконання лабораторної роботи я дізнався про такий метод сортування як сортування вставками, зрозумів принцип роботи даного методу та навчився використовувати його на практиці, створивши програму, яка сортує випадковий масив в порядку зростання. Також я дослідив та проаналізував властивості алгоритму за яким працює моя програма, а саме залежність часу роботи алгоритму в залежності від кількості вхідних даних, побудував графік залежності та порівняв його з теоретичними розрахунками.

Лабораторна робота Теорія алгоритмів

exellman

26.10.2018 09:38

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись