Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розробка та дослідження ефективності методів сортування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2024
Тип роботи:
Звіт до лабораторної роботи
Предмет:
СП
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
Кафедра ЕОМ
/
Розробка та дослідження ефективності методів сортування
ЗВІТ
до лабораторної роботи № 3
з дисципліни
" AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ"
МЕТА РОБОТИ
Вивчення, реалізація та дослідження ефективності методів сортування даних.
2. ТЕОРЕТИЧНІ ВІДОМОСТІ
2.1. Задача сортування
Задача сортування в програмуванні не вирішена повністю. Адже, хоча й існує велика кількість алгоритмів сортування, все ж таки метою програмування є не лише розробка алгоритмів сортування елементів, але й розробка саме ефективних алгоритмів сортування.
Ми знаємо, що одну й ту саму задачу можна вирішити за допомогою різних алгоритмів і кожен раз зміна алгоритму приводить до нових, більш або менш ефективних розв'язків задачі. Основними вимогами до ефективності алгоритмів сортування є перш за все часова ефективність та економне використання пам'яті. Згідно цих вимог, прості алгоритми сортування (такі, як сортування вибором і сортування вставкою) не є дуже ефективними.
Алгоритм сортування обміном, хоча і завершує свою роботу (оскільки він використовує лише цикли з параметром і в тілі циклів параметри примусово не змінюються) і не використовує допоміжної пам'яті, але займає багато часу. Навіть, якщо внутрішній цикл не містить жодної перестановки, то дії будуть повторюватись до тих пір, поки не завершиться зовнішній цикл.
Алгоритм сортування вибором ефективніше сортування обміном за критерієм М(n), тобто за кількістю перестановок, але також є не дуже ефективним. З цих причин було розроблено деякі нові алгоритми сортування, що отримали назву швидких алгоритмів сортування. Це такі алгоритми, як сортування деревом, пірамідальне сортування, швидке сортування Хоара та метод цифрового сортування.
Метою роботи є ознайомлення з алгоритмами сортування, спроба проаналізувати їх і написати програму, яка б виконувала сортування деякої послідовності за допомогою різних алгоритмів сортування.
Необхідність відсортувати які-небудь величини виникає в програмуванні дуже часто. Існують ситуації, коли попереднє сортування даних дозволяє скоротити змістовну частину алгоритму в декілька разів, а час його роботи - у десятки разів.
Однак справедливе й зворотне. Яким би гарним і ефективним не був обраний алгоритм, але якщо в якості підзадачі він використовує "поганє" сортування, то вся робота з його оптимізації виявляється марною. Невдало реалізоване сортування вхідних даних здатне помітно знизити ефективність алгоритму в цілому.
ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ
Задати послідовність цілих чисел довільної довжини і представити її у пам’яті комп’ютера у вигляді масиву або лінійного зв’язаного списку. Програмно реалізувати один із вказаних нижче методів сортування згідно з варіантом. Під час виконання програми обов’язково виводити на екран монітора всі проміжні кроки процесу сортування.
Провести дослідження побудованого методу за такою схемою:
1). Обґрунтувати вибір структури даних, в якій має зберігатись інформація (масив чи список; якщо список, то однозв’язаний чи двозв’язаний).
2). Намалювати схему алгоритму на прикладі послідовності з десяти (або більше при необхідності) цілих чисел, показуючи всі проміжні кроки процесу сортування.
3). Дослідити метод cортування на стійкість.
4). Дослідити метод cортування на економність використання пам’яті.
5). Дослідити метод на можливу специфіку вхідної послідовності (чи може послідовність містити елементи з однаковими ключами, чи має бути вхідна послідовність частково відсортована, чи мають елементи послідовності знаходитись у певному діапазоні і т.п.).
6). Дослідити ефективність методу. Для цього визначити значення кількості порівнянь (С) і кількості перестановок (М) в найкращому () і в найгіршому () випадках. Середні значення кількості порівнянь () і кількості перестановок () визначити, як середнє арифметичне для кожної величини від великої кількості спроб сортування випадкових послідовностей.
7). Визначити до якого класу (підкласу) належить досліджуваний метод. Використовуючи методику аналізу основних алгоритмічних конструкцій та визначення набору "елементарних" операцій, обчислити складність методу, що характеризується функцією трудомісткості. Зробити висновки про ефективність методу.
1.Пірамідальне сортування.
Результат виконання програми.
/
Текст програми:
PyramidSorting.cs:
using System;
namespace Lab2
{
class PyramidSorting
{
//додати 1 елемент піраміди
static int Add2Pyramid(double[] arr, int i, int N)
{
int imax;
double buf;
if ((2 * i + 2) < N)
{
if (arr[2 * i + 1] < arr[2 * i + 2])
{
imax = 2 * i + 2;
}
else
{
imax = 2 * i + 1;
}
}
else imax = 2 * i + 1;
if (imax >= N)
{
return i;
}
if (arr[i] < arr[imax])
{
buf = arr[i];
arr[i] = arr[imax];
arr[imax] = buf;
if (imax < N / 2)
{
i = imax;
}
}
return i;
}
public static void Sorting(double[] arr, int len)
{
//Крок 1. Створення піраміди
for (int i = len / 2 - 1; i >= 0; --i)
{
long prev_i = i;
i = Add2Pyramid(arr, i, len);
if (prev_i != i)
{
++i;
}
}
//Kрок 2: сортування
double buf;
for (int k = len - 1; k > 0; --k)
{
buf = arr[0];
arr[0] = arr[k];
arr[k] = buf;
int i = 0, prev_i = -1;
while (i != prev_i)
{
prev_i = i;
i = Add2Pyramid(arr, i, k);
}
}
}
}
}
Program.cs:
using System;
namespace Lab2
{
class Program
{
static void Main(string[] args)
{
double[] arr = new double[20];
//fill the array with random numbers
Random rd = new Random();
Console.WriteLine("Масив до сортування:");
for (int i = 0; i < arr.Length; ++i)
{
arr[i] = rd.Next(1, 21);
Console.Write(arr[i] + " ");
}
PyramidSorting.Sorting(arr, arr.Length);
Console.WriteLine("\n\nМасив пiсля сортування:");
for (int i = 0; i < arr.Length; ++i)
{
Console.Write(arr[i] + " ");
}
Console.ReadLine();
}
}
}
Висновок: Вивчив реалізацію та дослідження ефективності методів сортування даних.
29.03.2016 08:03-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора