Методи сортування. Звіт до лабораторної роботи з Програмування складних алгоритмів. Робота № 100305

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

Методи сортування

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

ВУЗ:

Національний технічний університет України Київський політехнічний інститут

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

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

Рік:

2022

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Програмування складних алгоритмів

Завантажити

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

Національний технічний університет України «Київський політехнічний інститут імені Ігоря Сікорського» ЗВІТ до лабораторної роботи № 3 з дисципліни «Програмування складних алгоритмів» Тема «Методи сортування» Варіант № 24 Дата «12» квітня 2022 Лабораторна робота № 3: Мета роботи: Метою лабораторної роботи є набуття практичних навичок з використання простих методів сортування. Завдання до роботи Методичні вказівки Лабораторна робота спирається на знаннях отриманих при вивченні наступних питань лекції: – Поняття сортування. – Різних методів сортування. Завдання до лабораторної роботи: Розробити програму з алгоритмом згідно варіанту з використанням методів сортування. Оцінити час виконання та складність алгоритму. 1. Провести сортування масивів вказаним методом та у вказаному порядку. Для тестування алгоритмів сортування масив (10x10, та більше бажанням). 2. Самостійно обрати додатковий метод та провести сортування того ж масиву. 3. Порівняти кількість перестановок (або час виконання) обох методів. Спробувати порівняти час виконання сортування з масивом більшого розміру, який створити за допомогою генератора випадкових чисел Завдання / / 1.2. Теоретичні відомості Алгоритм сортування— процес, що впорядковує множину однотипних елементів за певною ознакою (ключем сортування). Сортування є типовою проблемою обробки даних, що забезпечує розміщення елементів невпорядкованого набору значень в порядку монотонного зростання або спадання значення ключа. Основні методи сортування масивів: Бульбашкове сортування — у вхідній послідовності порівнюються два сусідні елементи і, якщо вони не відповідають критерію сортування, ці елементи міняються місцями. Алгоритм працює доти, доки весь масив даних не буде впорядковано. Часова складність — O(n2). Сортування вставками — елементи вхідної послідовності проглядаються по одному, і кожен новий елемент, що надійшов, розміщується в придатне місце серед раніше упорядкованих елементів. Застосовується для майже цілком відсортованих даних та даних невеликого розміру. Часова складність — O(n2). Сортування вибором — поєднання бульбашкового сортування та сортування вставками. Як і у бульбашкового сортування, цей алгоритм проходить масивом раз за разом, переміщаючи одне значення на правильну позицію. Однак, на відміну від бульбашкового сортування, вибирає найменше невідсортоване значення замість найбільшого. Як і при сортуванні вставками, упорядкована частина масиву розташована на початку, тоді як у бульбашкового сортування — наприкінці. Часова складність — O(n2). Швидке сортування — алгоритм, який не потребує додаткової пам’яті, оскільки використовує прості цикли й операції, працює швидше за інші алгоритми, що мають таку ж асимптотичну оцінку складності. З масиву обирається опорний елемент, і весь масив розбивається на дві частини: в першій — елементи, не більші даного, в другій — не менші. Впорядкування кожної з частин відбувається рекурсивно. Час роботи алгоритму сортування залежить від того, який елемент обрано як опорний. У найгіршому випадку час роботи алгоритму — O(n2), але математичне очікування часу роботи алгоритму на всіх можливих вхідних масивах ближче до найкращого — O(n log n). 1.3. Результати роботи Завдання 1. Написано програмний код, який реалізує задачу відсортувати масив відповідно до наданого зразку. Сортування здійснюється за допомогою обмінного методу quickSort. Для порівняння швидкості роботи алгоритму додатково розроблено метод сортування bubbleSort.. У найгіршому випадку часова складність першого алгоритму — O(n2), але математичне очікування часу роботи алгоритму на всіх можливих вхідних масивах ближче до найкращого — O(n log n). Часова складність другого алгоритму — O(n2). Нижче в таблиці представлено залежність часу виконання від розмірів масиву та відповідно кількості ітерацій. Спосіб сортування Розмір N*M Час виконання Бульбашкове сортування 10*10 0,011 ms 1000*1000 131,592 ms Швидке сортування 10*10 0,015 ms 1000*1000 21,373 ms 1.4. Висновки по роботі При виконанні лабораторної роботи №2 було отримано практичні навички з програмування алгоритмів сортування масиву. З отриманих результатів, які подані у таблиці , можна зробити висновок ,що метод швидкого сортування працює значно швидше ніж бульбашкове сортування, це не дивно , адже складність бульбашкового сортування для звичайного одномірного масиву в середньому O(n^2) ,а для швидкого сортування O(n*log n). 1.5. Лістинг програми package Algoritm.ua;import java.util.Scanner;import java.util.concurrent.atomic.AtomicLong;public class Main { public static void main(String[] args) { System.out.print("Enter a number of method (quick- or bubble-sort) you want to see(1-2):"); Scanner scan = new Scanner(System.in); int task = scan.nextInt(); System.out.println("Choose array size(1-2)"); System.out.println("1. 10✕10"); System.out.println("2. 1000✕1000"); //System.out.println("3. 100✕100"); int sizeArray = scan.nextInt(); if (sizeArray == 1) { int[][] array1 = new int[10][10]; initialization(array1); System.out.println("\nRedacted"); AtomicLong time = new AtomicLong(System.nanoTime()); if (task == 1) executionTask1(array1); if (task == 2) executionTask2(array1); time.set(System.nanoTime() - time.get()); printArray(array1); System.out.printf("Elapsed %,9.3f ms\n", time.get() / 1_000_000.0); } if (sizeArray == 2) { int[][] array1 = new int[1000][1000]; initialization(array1); System.out.println("\nRedacted"); AtomicLong time = new AtomicLong(System.nanoTime()); if (task == 1) executionTask1(array1); if (task == 2) executionTask2(array1); time.set(System.nanoTime() - time.get()); printArray(array1); System.out.printf("Elapsed %,9.3f ms\n", time.get() / 1_000_000.0); } } public static void quickSort(int[][] array, int low, int high, int column) { if (low >= high) return;//Закінчити, якщо більше немає що робити // Вибирається опорний елемент int middle = low + (high - low) / 2; int opora = array[middle][column]; // Поділити на підмасиви, по обидві сторони від опорного елементу int low1 = low, high1 = high; while (low1 <= high1) { while (array[low1][column] > opora) { low1++; } while (array[high1][column] < opora) { high1--; } if (low1 <= high1) {//Міняємо місцями int temp = array[low1][column]; array[low1][column] = array[high1][column]; array[high1][column] = temp; low1++; high1--; } } // Виклик рекурсії для сортування лівої й правої частини if (low < high1) quickSort(array, low, high1,column); if (high > low1) quickSort(array, low1, high,column); } public static void executionTask1(int[][] array) { for (int j = 0, i = 0; j < array[0].length; j++) { int sizeOfChangingArray; if (j >= (int) array[i].length/2) sizeOfChangingArray = array[i].length - j -1; else sizeOfChangingArray = j; int low = array.length - sizeOfChangingArray-1; int high = array.length-1; quickSort(array,low,high,j); } } public static void bubbleSort(int[][] arr,int low, int high, int column ) { if (low >= high) return;//Закінчити, якщо більше немає що робити int low1 = low, high1 = high; int length = arr.length; int temp = 0; for(int i=low1, k = 0; i < length-1; ++i,++k){ for(int j=low1; j < (length-k-1); ++j){ if(arr[j+1][column] > arr[j][column]){ //swap elements temp = arr[j][column]; arr[j][column] = arr[j+1][column]; arr[j+1][column] = temp; } } } } public static void executionTask2(int[][] array) { for (int j = 0, i = 0; j < array[0].length; j++) { int sizeOfChangingArray; if (j >= (int) array[i].length/2) sizeOfChangingArray = array[i].length - j -1; else sizeOfChangingArray = j; int low = array.length - sizeOfChangingArray-1; int high = array.length-1; bubbleSort(array,low,high,j); } } // Виведення переданого масиву public static void printArray(int[][] arr) { for (int i = 0; i < arr.length; i++) { for (int j = 0; j < arr[0].length; j++) { System.out.printf("%3d", arr[i][j]); } System.out.println(); } } // Ініціалізація випадковими числами public static void initialization(int[][] array) { for (int i = 0; i < array.length; i++) { for (int j = 0; j < array[0].length; j++) { array[i][j] = (int) (Math.random() * 20) - 10; System.out.printf("%3d", array[i][j]); } System.out.println(); } }} Результат виконання: - quickSort методом (масив 10*10) / - quickSort методом (масив 1000*1000) / - bubbleSort методом (масив 10*10) / - bubbleSort методом (масив 1000*1000) /

Звіт до лабораторної роботи Програмування складних алгоритмів

09.05.2023 18:05-

Коментарі

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

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

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

поділитись