НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ УКРАЇНИ “КИЇВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ імені ІГОРЯ СІКОРСЬКОГО” ЗВІТ з лабораторної роботи №3 з навчальної дисципліни “Програмування складних алгоритмів” Тема: Методи сортування Варіант 7 Київ 20____ І. Мета: Метою лабораторної роботи є набуття практичних навичок з використання простих методів сортування. Теоретична частина Сортування вставкою: Сортування масивів методом вставки(включенням) здійснюються таким чином. Масив розділяється на дві частини: відсортовану й невідсортовану. Елементи з невідсортованої частини по черзі вибираються й вставляються у відсортовану частину так, щоб не порушити в ній упорядкованість елементів. На початку роботи алгоритму за відсортовану частину масиву приймають тільки один перший елемент, а за невідсортовану частину - всі інші елементи. Таким чином, алгоритм буде складатися з n-1-го проходу (n - розмірність масиву), кожний з яких буде включати чотири дії: - взяття чергового i-го невідсортованого елемента й збереження його в додатковій змінній; - пошук позиції j у відсортованій частині масиву, у якій наявність узятого елемента не порушить упорядкованості елементів; - зсув елементів масиву від i-1-го до j-го вправо, щоб звільнити знайдену позицію вставки; - вставка взятого елемента в знайдену j-ю позицію. Сортування вибором: Сортування масивів методом вибору (виділення) здійснюються таким чином. Знаходимо (вибираємо) у масиві елемент із мінімальним значенням на інтервалі від 1- го елемента до n-го (останнього) елемента й міняємо його місцями з першим елементом. На другому кроці знаходимо елемент із мінімальним значенням на інтервалі від 2-го до n-го елемента й міняємо його місцями із другим елементом. І так далі для всіх елементів до n-1-го. ІІ. Завдання: / Завдання по варіанту Метод сортування вибором / Оцінка складності алгоритму Складність алгоритму сортування вибором в усіх випадках – O(n^2). Складність алгоритму сортування вставками в середньому – O(n^2), а у кращому випадку – O(n). Спосіб сортування Розмір N*N Час виконання  Сортування вибором 10*10 15100нс   100*100 3111500нс   250*250 8833000нс   500*500 49134400нс  Сортування вставками 10*10 16200нс   100*100 3564000нс   250*250 7847100нс   500*500 27690600нс  Виділено числа з меншим часом виконування алгоритму на певному обсязі масиву. Можна зробити висновок, що на меших обсягах час виконання алгоритму сортування вибором бистріший, а алгоритм сортування вставками швидший на більших обсягах даних. ІІІ. Результати виконання лабораторної роботи. / Блок-схема // // Програмний код import java.util.*; public class LR3 { public static void main(String[] args) { Scanner scan = new Scanner(System.in); System.out.print("Введіть розмір масиву: "); int n = scan.nextInt(); int[][] arr = new int[n][n]; for (int i = 0; i < arr.length; i++) for(int j = 0; j < arr.length; j++) arr[i][j] = (int) (Math.random() * 101) - 50; int[][] copy = new int[n][n]; for (int i = 0; i < copy.length; i++) System.arraycopy(arr[i], 0, copy[i], 0, copy.length); System.out.println("Початковий масив:"); printArr(arr); long firstTime = System.nanoTime(); selectionSort(arr); firstTime = System.nanoTime() - firstTime; System.out.println("\nМасив після сортування вибором:"); printArr(arr); System.out.println("\nЧас виконання сортування вибором: " + firstTime + " наносекунд."); long secondTime = System.nanoTime(); insertionSort(copy); secondTime = System.nanoTime() - secondTime; System.out.println("\nМасив після сортування вставками:"); printArr(arr); System.out.println("\nЧас виконання сортування вставками: " + secondTime + " наносекунд."); } public static void printArr(int[][] arr) { for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr.length; j++) { System.out.print(arr[i][j] + "\t"); } System.out.println(); } } public static void selectionSort(int[][] arr) { for(int i=0;i<arr.length;i++) { for (int j = i; j < arr.length; j++) { int pos = j; for (int k = j + 1; k < arr.length; k++) if (arr[i][k] > arr[i][pos]) pos = k; int temp = arr[i][pos]; arr[i][pos] = arr[i][j]; arr[i][j] = temp; } } } public static void insertionSort(int[][] arr) { for (int i = 0; i < arr.length; i++) { for (int j = 1+i; j < arr.length; j++) { int key = arr[i][j]; int k = j - 1; while (k >= i && arr[i][k] < key) { arr[i][k + 1] = arr[i][k]; k = k - 1; } arr[i][k + 1] = key; } } } } IV. Висновки. Написано програму, що сортує масив двома способами: вставками та вибором. Було визначено, що сортування вставками набагато бистріше при сортуванні великих масивів, а сортування вибором показує трохи кращі результати лише при сортуванні малих масивів.