Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Аналіз алгоритму сортування методом вставки
Інформація про навчальний заклад
ВУЗ:
Вінницькій національний технічний університет
Інститут:
Не вказано
Факультет:
інформаційних технологій та комп ютерної інженерії
Кафедра:
Не вказано
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Теорія алгоритмів
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки України
Вінницький національний технічний університет
Факультет інфотмаційних технологій та комп’ної інженерії
Кафедра комп’ютерних наук
Лабораторна робота №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 с
Для невідсортованого масиву
Для відсортованого по спаданню масиву
На виході ми отримуємо параболічну залежність часу від кількості вхідних даних.
Ми можемо теоретично розрахувати час виконання алгоритму за формулами:
(Для кращого випадку)
(Для гіршого випадку)
Якщо порівняти результати на практиці з теоретичними розрахунками часу виконання алгоритму в найгіршому і найкращому випадку, то можемо побачити що параболічна залежність зберігається.
Висновок: під час виконання лабораторної роботи я дізнався про такий метод сортування як сортування вставками, зрозумів принцип роботи даного методу та навчився використовувати його на практиці, створивши програму, яка сортує випадковий масив в порядку зростання. Також я дослідив та проаналізував властивості алгоритму за яким працює моя програма, а саме залежність часу роботи алгоритму в залежності від кількості вхідних даних, побудував графік залежності та порівняв його з теоретичними розрахунками.
26.10.2018 09:10-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора