Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка та дослідження ефективності методів сортування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2024
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи обчислень
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки
Національний університет “Львівська політехніка”
Кафедра ЕОМ
/
Звіт
з лабораторної роботи № 3
з дисципліни: “Алгоритми та методи обчислень”
на тему: “Розробка та дослідження ефективності методів сортування”
Мета лабораторної роботи
Вивчення, реалізація та дослідження ефективності методів сортування даних.
Теоретичні відомості
Задача сортування в програмуванні не вирішена повністю. Адже, хоча й існує велика кількість алгоритмів сортування, все ж таки метою програмування є не лише розробка алгоритмів сортування елементів, але й розробка саме ефективних алгоритмів сортування.
Ми знаємо, що одну й ту саму задачу можна вирішити за допомогою різних алгоритмів і кожен раз зміна алгоритму приводить до нових, більш або менш ефективних розв'язків задачі. Основними вимогами до ефективності алгоритмів сортування є перш за все часова ефективність та економне використання пам'яті. Згідно цих вимог, прості алгоритми сортування (такі, як сортування вибором і сортування вставкою) не є дуже ефективними.
Алгоритм сортування обміном, хоча і завершує свою роботу (оскільки він використовує лише цикли з параметром і в тілі циклів параметри примусово не змінюються) і не використовує допоміжної пам'яті, але займає багато часу. Навіть, якщо внутрішній цикл не містить жодної перестановки, то дії будуть повторюватись до тих пір, поки не завершиться зовнішній цикл.
Алгоритм сортування вибором ефективніше сортування обміном за критерієм М(n), тобто за кількістю перестановок, але також є не дуже ефективним. З цих причин було розроблено деякі нові алгоритми сортування, що отримали назву швидких алгоритмів сортування. Це такі алгоритми, як сортування деревом, пірамідальне сортування, швидке сортування Хоара та метод цифрового сортування.
Метою роботи є ознайомлення з алгоритмами сортування, спроба проаналізувати їх і написати програму, яка б виконувала сортування деякої послідовності за допомогою різних алгоритмів сортування.
Необхідність відсортувати які-небудь величини виникає в програмуванні дуже часто. Існують ситуації, коли попереднє сортування даних дозволяє скоротити змістовну частину алгоритму в декілька разів, а час його роботи - у десятки разів.
Індивідуальне завдання
Варіант 2
Задати послідовність цілих чисел довільної довжини і представити її у пам’яті комп’ютера у вигляді масиву або лінійного зв’язаного списку. Програмно реалізувати один із вказаних нижче методів сортування згідно з варіантом:
Рекурсивне сортування злиттям.
Код програми
#include <iostream>
#include <conio.h>
#include <ctime>
using namespace std;
template<typename T>
void merge_sort(T array[], unsigned int left, unsigned int right)
{
if (left < right)
{
unsigned int middle = (left + right) / 2;
merge_sort(array, left, middle);
merge_sort(array, middle + 1, right);
unsigned int pos1 = left;
unsigned int pos2 = middle + 1;
unsigned int temp_index = 0;
T *temp = new T[right - left + 1];
while (pos1 <= middle && pos2 <= right)
{
if (array[pos1] < array[pos2])
temp[temp_index++] = array[pos1++];
else
temp[temp_index++] = array[pos2++];
}
while (pos2 <= right)
temp[temp_index++] = array[pos2++];
while (pos1 <= middle)
temp[temp_index++] = array[pos1++];
for (temp_index = 0; temp_index < right - left + 1; temp_index++)
array[left + temp_index] = temp[temp_index];
delete[] temp;
}
}
template<typename T>
void merge_sort(T array[], unsigned int length)
{
merge_sort(array, 0, length - 1);
}
void main()
{
srand((unsigned int)time(nullptr));
const unsigned int length = 10;
int array[length];
for (int i = 0; i < length; i++)
{
array[i] = rand() % 1000;
}
merge_sort(array, length);
for (int i = 0; i < length; i++)
{
cout << array[i] << " ";
}
cout << endl;
_getch();
}
Результат виконання програми
/
Висновок
Я вивчив, реалізував та дослідив ефективність методів сортування даних.
30.03.2016 11:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора