НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №3 з навчальної дисципліни “Програмування складних алгоритмів” Тема: «МЕТОДИ СОРТУВАННЯ» Варіант 13 Київ 2022 Мета: Метою лабораторної роботи є набуття практичних навичок з використання простих методів сортування. Теоретичні відомості Сортування вибором — простий алгоритм сортування лінійного масиву, на основі вставок. Має ефективність n2, що робить його неефективним при сортування великих масивів, і в цілому, менш ефективним за подібний алгоритм сортування включенням. Сортування вибором вирізняється більшою простотою, ніж сортування включенням, і в деяких випадках, вищою продуктивністю. Сортування включенням або сортування вставлянням — простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг: 1 - простота у реалізації 2 - ефективний (зазвичай) на маленьких масивах 3 - ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна O(n + d), де d — кількість інверсій 4 - на практиці ефективніший за більшість інших квадратичних алгоритмів (O(n2)), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n2/4, і в найкращому випадку є лінійною 5 - є стабільним алгоритмом. Наприклад, більшість людей при сортуванні колоди гральних карт, використовують метод, схожий на алгоритм сортування включенням. Сортування злиттям (англ. merge sort) — алгоритм сортування, в основі якого лежить принцип «Розділяй та володарюй». В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається — тоді решта іншої колони додається до нової. Під час сортування в дві допоміжні черги з основної поміщаються перші дві відсортовані підпослідовності, які потім зливаються в одну і результат записується в тимчасову чергу. Потім з основної черги беруться наступні дві відсортовані підпослідовності і так доти, доки основна черга не стане порожньою. Після цього послідовність з тимчасової черги переміщається в основну чергу. І знову продовжується сортування злиттям двох відсортованих підпослідовностей. Сортування триватиме доти, доки довжина відсортованої підпослідовності не стане рівною довжині самої послідовності. / / Сортування вставками + додатково вибором. / Результат роботи Виконання алгоритму масиву лише 10 * 10 / Також розмірність звеличина до 1000 * 1000 для аналізу різниці швидкостей: / Висновки: розроблено програму, що виконує два рази той же самий алгоритм в основі якого лежить сортування, але з різницею в методах сортування. Перший раз використано алгоритм сортування вставкою, а наступний алгоритм вибором. У результаті порівняно час, затрачений на різні методи сортування, і виявилося, що сортування вставками швидше на 6 мілісекунд, ніж сортування вибором. Програмний код public class Lr3 { public static void main(String[] args) { int side = 10; int[][] arr = generateArr(side); int[][] arrCopy = copyArr(arr); System.out.println("Дано масив розмірностю " + side + ":"); displayArr(arr); System.out.println("\nВиконання сортування вставками:"); long time = System.currentTimeMillis(); for (int j = side-1; j > 0; j--) { int[] subArr = new int[j]; for (int i = (side-1 - j) + 1; i < side; i++) { subArr[i - ((side-1 - j) + 1)] = arr[i][j]; } insertionSort(subArr); for (int i = (side-1 - j) + 1; i < side; i++) { arr[i][j] = subArr[i - ((side-1 - j) + 1)]; } } displayArr(arr); System.out.println("Витрачено мілісекунд на сортування вставками (за варіантом): " + (System.currentTimeMillis() - time) + "\n"); System.out.println("Виконання сортування вибором:"); time = System.currentTimeMillis(); for (int j = side-1; j > 0; j--) { int[] subArr = new int[j]; for (int i = (side-1 - j) + 1; i < side; i++) { subArr[i - ((side-1 - j) + 1)] = arrCopy[i][j]; } selectionSort(subArr); for (int i = (side-1 - j) + 1; i < side; i++) { arrCopy[i][j] = subArr[i - ((side-1 - j) + 1)]; } } displayArr(arrCopy); System.out.println("Витрачено мілісекунд на сортування вибором (додатковий): " + (System.currentTimeMillis() - time)); } static void insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { for (int j = i; j > 0 && arr[j] < arr[j-1]; j--) { int temp = arr[j]; arr[j] = arr[j-1]; arr[j-1] = temp; } } } static void selectionSort(int[] arr) { for (int i = 0; i < arr.length; i++) { int min = arr[i]; int minIndex = i; for (int j = i; j < arr.length; j++) { if (arr[j] < min) { min = arr[j]; minIndex = j; } } int temp = arr[minIndex]; arr[minIndex] = arr[i]; arr[i] = temp; } } static int[][] copyArr (int[][] arr) { int[][] copied = new int[arr.length][arr[0].length]; for (int i = 0; i<arr.length; i++) { for (int j = 0; j < arr[i].length; j++) { copied[i][j] = arr[i][j]; } } return copied; } static int[][] generateArr(int side) { int[][] arr = new int[side][side]; for (int i = 0; i< side; i++) for (int j = 0; j < side; j++) arr[i][j] = (int)(Math.random() * 9); return arr; } static void displayArr(int[][] arr) { for (int i = 0; i < arr.length; i++) { System.out.println(Arrays.toString(arr[i])); } } }