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