Аналіз алгоритму сортування методом. Лабораторна робота з Теорiя алгоритмiв i математичнi основи представленння знань. Робота № 530483

Перехід до торгівельного партнера Binance

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

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

ВУЗ:

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

Інститут:

Інститут комп’ютерних наук та інформаційних технологій

Факультет:

ФІТКІ

Кафедра:

КН

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

Рік:

2024

Тип роботи:

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

Предмет:

Теорiя алгоритмiв i математичнi основи представленння знань

Група:

КН 2

Варіант:

Завантажити

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

Міністерство освіти і науки України Вінницький національний технічний університет Факультет інформаційних технологій і комп’ютерної інженерії Кафедра комп’ютерних наук Лабораторна робота №3З дисципліни: Теорія алгоритмів Тема: «Аналіз алгоритму сортування методом злиття» Вінниця, 2017 Аналіз алгоритму сортування методом злиття Мета: навчитись аналізувати алгоритми на прикладі алгоритму сортування методом злиття Сортування злиттям (англ. merge sort) — алгоритм сортування, в основі якого лежить принцип «Розділяй та володарюй». В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається — тоді решта іншої колони додається до нової. Під час сортування в дві допоміжні черги з основної поміщаються перші дві відсортовані підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу. Потім з основної черги беруться наступні дві відсортовані підпослідовності і так до тих пір доки основна черга не стане порожньою. Після цього послідовність з тимчасової черги переміщається в основну чергу. І знову продовжується сортування злиттям двох відсортованих підпослідовностей. Сортування триватиме до тих пір поки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності Приклад реалізації на Java public class Solution{ public static void main(String[] args) throws IOException { BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); System.out.println("Введіть кількість елементів масива"); int num = Integer.parseInt(reader.readLine()); int arr[] = new int[num]; System.out.println("Рaндомний массив:"); for(int i = 0; i < arr.length; i++) {//элементу массива присваивается случайное число от 0 до 99 arr[i] = (int)(Math.random() * 100); System.out.print(arr[i] + " "); } long timeout= System.currentTimeMillis(); mergesort(arr); timeout = System.currentTimeMillis() - timeout; System.out.println("Час затрачений на виконання сортування = "+ timeout+ "мc"); } public static void mergesort(int[] arr) { System.out.println("\nВідсортований масив:"); int n = arr.length; boolean c = true; int i = 0; int i1 = 0; int i2 = 0; int n1 = 0; int n2 = 0; int[] barr = new int[n]; int mergelen = 0; barr = new int[n]; mergelen = 1; while (mergelen < n) { if (c) { i = 0; while (i + mergelen <= n) { i1 = i + 1; i2 = i + mergelen + 1; n1 = i + mergelen; n2 = i + 2 * mergelen; if (n2 > n) { n2 = n; } while (i1 <= n1 | i2 <= n2) { if (i1 > n1) { while (i2 <= n2) { i = i + 1; barr[i - 1] = arr[i2 - 1]; i2 = i2 + 1; } } else { if (i2 > n2) { while (i1 <= n1) { i = i + 1; barr[i - 1] = arr[i1 - 1]; i1 = i1 + 1; } } else { if (arr[i1 - 1] > arr[i2 - 1]) { i = i + 1; barr[i - 1] = arr[i2 - 1]; i2 = i2 + 1; } else { i = i + 1; barr[i - 1] = arr[i1 - 1]; i1 = i1 + 1; } } } } } i = i + 1; while (i <= n) { barr[i - 1] = arr[i - 1]; i = i + 1; } } else { i = 0; while (i + mergelen <= n) { i1 = i + 1; i2 = i + mergelen + 1; n1 = i + mergelen; n2 = i + 2 * mergelen; if (n2 > n) { n2 = n; } while (i1 <= n1 | i2 <= n2) { if (i1 > n1) { while (i2 <= n2) { i = i + 1; arr[i - 1] = barr[i2 - 1]; i2 = i2 + 1; } } else { if (i2 > n2) { while (i1 <= n1) { i = i + 1; arr[i - 1] = barr[i1 - 1]; i1 = i1 + 1; } } else { if (barr[i1 - 1] > barr[i2 - 1]) { i = i + 1; arr[i - 1] = barr[i2 - 1]; i2 = i2 + 1; } else { i = i + 1; arr[i - 1] = barr[i1 - 1]; i1 = i1 + 1; } } } } } i = i + 1; while (i <= n) { arr[i - 1] = barr[i - 1]; i = i + 1; } } mergelen = 2 * mergelen; c = !c; } if (!c) { i = 1; do { arr[i - 1] = barr[i - 1]; i = i + 1; } while (i <= n); } System.out.println(Arrays.toString(barr)); }} Аналіз алгоритму На кожному кроці ми розбиваємо вихідний масив на дві рівні частини. Однак, в цьому випадку подальші обчислення відбуваються на обох частинах. Після повернення рекурсії ми застосовуємо до результатів операцію сортування, що займає Θ (n) часу. Отже, оригінальний масив розбитий на дві частини, розміром n / 2 кожна. Коли ми будемо їх з'єднувати, в операції братимуть участь n елементів, отже, час виконання буде Θ (n). Глибина рекурсивного дерева, дорівнює log (n). В результаті у нас log (n) рядків зі складністю Θ (n), отже, загальна складність mergeSort: Θ (n * log (n)). Це набагато краще, ніж Θ (n2), яку нам дає сортування вибором (log (n) набагато менше n, тому n * log (n) так само набагато менше n * n = n2). / Час роботи алгоритму T(n) по впорядкуванню n елементів задовільняє рекурентному співвідношенню: T(n) = 2T(n/2) + O(n), де T(n/2) - час на впорядкування половини масиву, O(n) - час на злиття половинок. Враховуючи, що T(1) = O(1), розвязком співвідношення є T(n) = O(n log n). Крім того, алгоритм потребує для своєї роботи O(n) додаткової памяті. Алгоритм не міняє порядок розташування однакових елементів, а отже він є стабільним. Висновок: алгоритм сортування методом злиття набагато вигідніший ніж попередньо розглянуті алгоритми, при великих обсягах вхідних даних. Проте якщо кількість вхідних даних мала то він менш ефективний ніж такі алгоритми сортування як сортування вставками, вибором та сортування методом бульбашки. Також перевагами даного алгоритму являються: • Працює навіть на структурах даних послідовного доступу. • Добре поєднується з підкачкою і кешуванням пам'яті. • Непогано працює в паралельному варіанті: легко розбити завдання між процесорами порівну, але важко зробити так, щоб інші процесори взяли на себе роботу, в разі якщо один процесор затримається. • Не має «важких» вхідних даних. • Стійка - зберігає порядок рівних елементів (що належать одному класу еквівалентності в порівнянні). А недоліки: • На «майже відсортованих» масивах працює так само довго, як на хаотичних. • Вимагає додаткової пам'яті за розміром вихідного масиву.

Лабораторна робота Теорiя алгоритмiв i математичнi основи представленння знань

exellman

24.10.2018 17:10-

Коментарі

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

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

Маєш корисні навчальні матеріали, які припадають пилом на твоєму комп'ютері? Розрахункові, лабораторні, практичні чи контрольні роботи — завантажуй їх прямо зараз і одразу отримуй бали на свій рахунок! Заархівуй всі файли в один .zip (до 100 МБ) або завантажуй кожен файл окремо. Внесок у спільноту – це легкий спосіб допомогти іншим та отримати додаткові можливості на сайті. Твої старі роботи можуть приносити тобі нові нагороди!

поділитись