Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Методи сортування
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
ЗВІТ
до лабораторної роботи № 3
з дисципліни «Програмування складних алгоритмів»
Тема «Методи сортування»
Варіант № 11
Лабораторна робота № 3:
Методи сортування
Мета: набуття практичних навичок з використання простих методів сортування.
1.1. Завдання до роботи
Провести сортування масивів вказаним методом та у вказаному порядку. Для тестування алгоритмів сортування масив (10x10, та більше бажанням). Самостійно обрати додатковий метод та провести сортування того ж масиву. Порівняти кількість перестановок (або час виконання) обох методів. Спробувати порівняти час виконання сортування з масивом більшого розміру, який створити за допомогою генератора випадкових чисел.
Завдання відповідно варіанту:
Метод сортування: сортування методом вставки.
/
1.2. Теоретичні відомості
Сортування даних – невід’ємна частина аналізу даних. Воно дає можливість відсортувати список імен в алфавітному порядку, скласти список продуктів за рівнем запасів (від найбільшого до найменшого) або впорядкувати рядки за кольорами чи піктограмами.
Алгоритм сортування - це алгоритм, який сортує масиви даних. Різні типи алгоритмів сортування включають:
сортування вибором (Selection Sort);
сортування вставкою (Insertion Sort);
сортування обміном (Bubble Sort);
швидке сортування (Quick Sort);
сортування підрахунком (Counting Sort) тощо.
Сортування вибором (Selection Sort) — простий алгоритм сортування лінійного масиву, на основі вставок. Має ефективність n2, що робить його неефективним при сортування великих масивів, і в цілому, менш ефективним за подібний алгоритм сортування включенням. Сортування вибором вирізняється більшою простотою, ніж сортування включенням, і в деяких випадках, вищою продуктивністю.
Для сортування масиву методом вибору від найменшого до найбільшого елементу виконуються наступні кроки:
Починаючи з елементу під індексом 0, шукаємо в масиві найменше значення.
Знайдене значення міняємо місцями з нульовим елементом.
Повторюємо кроки №1 і №2 уже для наступного індексу в масиві (відсортований елемент більше не чіпаємо).
Іншими словами, ми шукаємо найменший елемент в масиві і переміщуємо його на перше місце. Потім шукаємо другий найменший елемент і переміщуємо його вже на друге місце після першого найменшого елемента. Цей процес триває до тих пір, поки в масиві не закінчаться невідсортовані елементи.
Приклад коду:
for(int i = 0; i < N-1; i++)
{
int min_indx = i;
for(int j = i; j < N; j++)
{
if (mas[j] < mas[min_indx])
{
min_indx = j;
}
}
if (i != min_indx)
{
int tmp = mas[i];
mas[i] = mas[min_indx];
mas[min_indx] = tmp;
}
}
Сортування вставками (Insertion sort) - алгоритм сортування, в якому елементи вхідної послідовності проглядаються по одному, і кожен новий елемент, що надійшов, розміщується в відповідне місце серед раніше впорядкованих елементів. Обчислювальна складність – О(n2).
Приклад коду:
void Sort(int* arr, int n){
int counter = 0;
for(int i = 1; i < n; i++){
for(int j = i; j > 0 && arr[j-1] > arr[j]; j--){
counter++;
int tmp = arr[j-1];
arr[j-1] = arr[j];
arr[j] = tmp;
}
}
Cout << counter << endl;
}
Сортування обміном (також відоме як сортування методом бульбашки) полягає в тому, що всі сусідні елементі вихідного масиву попарно порівнюються один з одним і міняються місцями, якщо попередній елемент більший, або менший в залежності від типу сортування (за зростанням чи за спаданням) від наступного. В результаті максимальний (мінімальний) елемент поступово зміщується вправо і після першого такого перегляду займе крайнє праве положення. Потім процес перегляду повторюється, і своє місце займає другий за величиною елемент, який також виключається з подальшого розгляду. Продовжуючи даний процес далі, на останньому кроці отримаємо впорядковану послідовність. Обчислювальна складність – О(n2).
Приклад коду:
int x = 0;
for (int i = size - 1; i >= x; i--)
{
for (int j = size - 1; j >= x; j--) {
if (mas[j] < mas[j-1]) {
tmp = mas[j];
mas[j] = mas[j-1];
mas[j-1] = tmp;
cout << "елемент " << j << " помінявся з елементом " << j - 1 << " << " << endl;
}
}
x++;
}
Швидке сортування (Quick Sort) — алгоритм сортування, добре відомий, як алгоритм розроблений Чарльзом Гоаром, який не потребує додаткової пам'яті і виконує у середньому О(nlogn).операцій. Однак, у найгіршому випадку робить О(n2). порівнянь. Оскільки алгоритм використовує дуже прості цикли і операції, він працює швидше інших алгоритмів, що мають таку ж асимптотичну оцінку складності. Наприклад, зазвичай більш ніж удвічі швидший порівняно з сортуванням злиттям.
Ідея алгоритму полягає в переставлянні елементів масиву таким чином, щоб його можна було розділити на дві частини і кожний елемент з першої частини був не більший за будь-який елемент з другої. Впорядкування кожної з частин відбувається рекурсивно. Алгоритм швидкого сортування може бути реалізований як у масиві, так і в двозв'язному списку.
Швидке сортування є алгоритмом на основі порівнянь, і не є стабільним.
Приклад коду:
void QuickSort (int Array[], unsigned int N, int L, int R)
{
int iter = L, jter = R ;
int middle = (R+L)/2;
int x = Array [middle];
int w;
do
{
while (Array[iter]<x)
{
iter++;
}
while (x < Array[jter])
{
jter--;
}
if (iter <= jter)
{
w = Array [iter];
Array [iter] = Array [jter];
Array [jter] = w;
iter++;
jter--;
}
}
while (iter < jter);
if (L < jter)
{
QuickSort (Array, N, L, jter);
}
if (iter < R)
{
QuickSort (Array, N, iter, R);
}
}
Сортування підрахунком (Counting Sort) — алгоритм впорядкування, що застосовується при малій кількості різних елементів (ключів) у масиві даних. Час його роботи лінійно залежить як від загальної кількості елементів у масиві так і від кількості різних елементів. Ідея алгоритму полягає у тому, щоб підрахувати скільки разів кожен елемент зустрічається у вихідному масиві. Спираючись на ці дані можна одразу вирахувати на якому місці має стояти кожен елемент, а потім за один прохід поставити всі елементи на свої місця.
Приклад коду:
void couting_sort(vector<int> & array)
{
if (array.size() == 0) return;
auto p = minmax_element(array.begin(), array.end());
int min = *p.first;
int dist = *p.second - min + 1;
vector<int> t(dist,0);
for(auto i: array) t[i - min]++;
for(int i = 0, idx = 0; i < t.size(); ++i)
for(int j = 0; j < t[i]; ++j)
array[idx++] = i + min;
}
1.3. Результати роботи
Створено динамічний двовимірний масив розміру row*column та заповнено псевдовипадковими числами від 1 до 30 за допомогою функції rand().
Розроблено функцію insertionSort() для сортування даного масиву методом вставки. Вкладеним циклом for() проходимося по стовпцях і рядках(починаючи з другого) матриці. Умовно ділимо стовпець на дві частини: відсортовану (умовно) та невідсортовану. Для цього уводимо змінну key – ключ, з якого розпочинається невідсортований стовпець. Змінній k присвоюємо відсортовану частинку (наший перший елемент). Циклу while() задаємо умову якщо k >= 0 і відсортований елемент більший за ключ key. Таким чином ці елементи міняються місцями.
Розроблено функцію selectionSort() для сортування даного масиву методом вибором. Вкладеним циклом for() проходимося по стовпцях і рядках (до передостаннього, адже останній елемент не є таким важливим) матриці. Створюємо змінну min для знаходження індексу мінімального елементу, якому присвоюємо значення рядку і. Циклом for() проходимось вздовж другого рядка матриці. Умовним оператором if() перевіряємо умову: якщо перший елементи першого стовпця більший за другий, то запам’ятовуємо мінімальний елемент і міняємо їх місцями функцією swap().
Створюємо функцію рrint() для виведення матриць.
Таким чином виводиться три матриці: початкова, відсортована методом вставки та методом вибору.
Проведено оцінку часової складності алгоритмів обох сортувань.
Спосіб сортування
Розмір
Час виконання
Сортування методом вставки
10*10
0.00000213 с
50*50
0.00011209 с
100*100
0.00078796 с
500*500
0.130512 с
Сортування методом вибору
10*10
0.00000117 с
50*50
0.00007198 с
100*100
0.0006405 с
500*500
0.1451 с
1.4.Висновок:
У ході лабораторної роботи було ознайомлено з використанням простих методів сортування. Розроблено програму для сортування двовимірного масиву методом вставки та вибору, визначено час роботи дох алгоритмів. Обчислювальна складність обох методів – О(n2), але, як бачимо, сортування методом вибору є швидшим.
1.5. Лістинг програми:
#include <iostream>
#include <iomanip>
#include <chrono>
#include <ctime>
using namespace std;
void insertionSort(int** arr, int row, int column);
void selectionSort(int** arr, int row, int column);
void print(int** arr, int row, int column);
int main() {
srand(time(NULL));
int row, column;
cout << "Enter rows count: ";
cin >> row;
cout << "Enter columns count: ";
cin >> column;
int** arr = new int* [row];
for (int i = 0; i < row; i++)
arr[i] = new int[column];
cout << "Initial matrix:" << endl;
for (int i = 0; i < row; i++)
{
for (int j = 0; j < column; j++)
{
arr[i][j] = rand() % 30 + 1;
cout << setw(5) << arr[i][j] << " ";
}
cout << endl;
}
const auto beginning_1 = chrono::high_resolution_clock::now();
insertionSort(arr, row, column);
const auto end_1 = chrono::high_resolution_clock::now();
cout << endl << "Insertion sort:" << endl;
print(arr, row, column);
chrono::duration<float> duration1 = end_1 - beginning_1;
cout << "The operating time of the first sort: " << duration1.count() << endl;
const auto beginning_2 = chrono::high_resolution_clock::now();
selectionSort(arr, row, column);
const auto end_2 = chrono::high_resolution_clock::now();
cout << endl << "Selection sort:" << endl;
print(arr, row, column);
chrono::duration<float> duration2 = end_2 - beginning_2;
cout << "The operating time of the second sort: " << duration2.count() << endl;
for (int i = 0; i < row; i++)
delete[] arr[i];
delete[] arr;
return 0;
}
void insertionSort(int** arr, int row, int column)
{
for (int i = 0; i < column; i++)
{
for(int j = 1; j < row; j++)
{
int key = arr[j][i];
int k = j - 1;
while(k >= 0 && arr[k][i] < key)
{
arr[k + 1][i] = arr[k][i];
arr[k][i] = key;
k--;
}
}
}
}
void selectionSort(int** arr, int row, int column)
{
for (int k = 0; k < column; k++)
{
for (int i = 0; i < row - 1; i++)
{
int min = i;
for (int j = i + 1; j < row; j++)
{
if (arr[j][k] > arr[min][k])
min = j;
}
swap(arr[i][k], arr[min][k]);
}
}
}
void print(int** arr, int row, int column)
{
for (int i = 0; i < row; i++)
{
for (int j = 0; j < column; j++)
{
cout << setw(5) << arr[i][j] << " ";
}
cout << endl;
}
}
1.6. Результат:
/
/
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора