Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Дослідження ефективності методів сортування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2013
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Інші
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти і науки, молоді та спорту України
Національний університет “Львівська політехніка”
Кафедра ЕОМ
Звіт
з лабораторної роботи № 6
на тему:
«Дослідження ефективності методів сортування»
з дисципліни:
"AЛГОРИТМИ ТА МЕТОДИ ОБЧИСЛЕНЬ"
№ варіанта = 12
Мета роботи.
Вивчення і програмна реалізація методів сортування даних та дослідження їх ефективності.
Постановка задачі.
2.1. Загальна частина
Програмно реалізувати один із вказаних нижче методів сортування згідно з варіантом. Вхідну послідовність цілих чисел довільної довжини вводити з клавіатури (0 – признак кінця вводу послідовності). Зберігати послідовність в пам’яті комп’ютера у вигляді масиву або лінійного зв’язаного списку (однонаправленого або двонаправленого за власним вибором). Під час виконання програми обов’язково виводити на екран монітора всі проміжні кроки процесу сортування.
Провести дослідження побудованого методу за схемою:
1) Намалювати схему алгоритму на прикладі послідовності з десяти (або більше при необхідності) цілих чисел, показуючи всі проміжні кроки процесу сортування.
2) Дослідити метод cортування на стійкість.
3) Дослідити метод cортування на економність використання пам’яті.
4) Дослідити метод на можливу специфіку вхідної послідовності (чи може послідовність містити елементи з однаковими ключами, чи має бути вхідна послідовність частково відсортована, чи мають елементи послідовності знаходитись у певному діапазоні і т.п.).
5) Дослідити ефективність методу. Для цього програмно визначити значення кількості порівнянь (С) і кількості перестановок (М) в найкращому () і в найгіршому () випадках. Для середнього випадку кількість порівнянь () і кількість перестановок () визначити для кожної величини як середнє арифметичне значення від великої кількості спроб сортування послідовностей випадкових чисел. Побудувати графіки залежностей , , , від кількості елементів n, де n змінюється від 1 до 100 000.
6) Визначити до якого класу (підкласу) належить досліджуваний метод. Використовуючи методику аналізу основних алгоритмічних конструкцій та визначення набору "елементарних" операцій, обчислити складність методу, що характеризується функцією трудомісткості.
2.2. Індивідуальне завдання
А. Послідовність представлена в пам’яті комп’ютера у вигляді масиву:
12. Сортування злиттям.
Опис алгоритму.
В основі цього способу сортування лежить злиття двох упорядкованих ділянок масиву в одну впорядковану ділянку іншого масиву. Злиття двох упорядкованих послідовностей можна порівняти з перебудовою двох колон солдатів, вишикуваних за зростом, в одну, де вони також розташовуються за зростом. Якщо цим процесом керує офіцер, то він порівнює зріст солдатів, перших у своїх колонах і вказує, якому з них треба ставати останнім у нову колону, а кому залишатися першим у своїй. Так він вчиняє, поки одна з колон не вичерпається – тоді решта іншої колони додається до нової.
Дослідження методу.
Схема алгоритму cортування на прикладі послідовності чисел.
Послідовність: 31 26 10 46 49 28 3 19 12
Крок:
Послідовність:
1
31 | 26 | 10 | 46 | 49 | 28 | 3 | 19 | 12
2
31 26 | 10 46 | 49 28 | 3 19 | 12
26 31 | 10 46 | 28 49 | 3 19 | 12
3
26 31 10 46 | 28 49 3 19 | 12
10 26 31 46 | 3 19 28 49 | 12
4
10 26 31 46 3 19 28 49 | 12
3 10 19 26 28 31 46 49 | 12
Результат:
3 10 12 19 26 28 31 46 49
Дослідження методу cортування на стійкість.
Якщо в масиві будуть однакові елементи, то вони не змінять свої позиції.
Метод сортування стійкий.
Дослідження методу cортування на економність використання пам’яті.
Серйозним недоліком цього алгоритму є необхідність додаткового масиву такої ж довжини, як і в основного. За великих довжин можлива ситуація, коли на один масив пам'яті вистачає, а на два – ні. Тому даний метод не є економний відносно використання пам’яті.
Дослідження методу на специфіку вхідної послідовності.
Вхідна послідовність може бути будь-яка, тобто містити однокові елементи, може бути, може не бути відсортованою, або є частково відсортована, однакові елементи можуть знаходитись в будь-якому діапазоні, відсортована буде будь-яка послідовність.
Дослідження ефективності методу.
1) Програмні дослідження.
а) Кількість порівнянь в найкращому, в найгіршому та в середньому випадках.
Кількість порівнянь у всіх випадках буде однаковою, тому що всі елементи порівнюються, від початку і до кінця масиву.
б) Кількість перестановок в найкращому, в найгіршому та в середньому випадках.
в найкращому = 0 ({3, 10, 12, 19, 26, 28, 31, 46, 49})
в найгіршому = 29 ({49, 46, 31, 28, 26, 19, 12, 10, 3})
в середньому = 11 ({28, 3, 19, 12, 10, 26, 31, 49, 46})
2) Чисельні дослідження.
а) Визначення класу (підкласу) алгоритму відносно його трудомісткості.
Клас NPR – клас кількісно-параметрично залежних по трудомісткості алгоритмів. Це досить широкий клас алгоритмів, тому що в більшості практичних випадків функція трудомісткості залежить як від кількості даних на вході, так і від їхніх значень.
Підклас NPRE (Equivalent) – підклас алгоритмів, у трудомісткості яких складова має порядок росту
Таким чином, для алгоритмів цього підкласу вплив на головний порядок функції трудомісткості параметричного компоненту має той самій порядок (в мультиплікативній формі), що й кількісного компоненту. Для алгоритмів, що відносяться до цього підкласу, можна говорити про квадратично-кількісну функцію трудомісткості. В цей підклас входить алгоритм сортування масиву методом бульбашки.
б) Обчислення функції трудомісткості алгоритму.
void Sort(int * mas, const int len)
{
int n = 1, l, m; //1
int *mas1;
while (n < len) //1
{
l = 0; //1
while (l < len) //1
{
if (l+n >= len) //2
break;
m = (l+n*2>len) ? (len-(l+n)) : n; //7
mas1 = HelpSort(mas + l, mas + l + n, n, m); //4
for (int i = 0; i<n+m; i++) //1 n+m повторень
mas[l+i] = mas1[i]; //4
delete [] mas1; //1
l += n*2; //3
for (unsigned k = 0; k < len; ++k) //1
}
n *= 2; //2
}
}
1+1*(1+1*(2+7+4+1+(n+m)*4+1+3+1)+2)=23+4n+4m
1+1*(1+1*(2+7+4+1+(n+m)*4+1+3+1)+2)=23+4n+4m
3) Асимптотичні дослідження.
а) Знаходження часової складності алгоритму ( за нотацією Ландау).
О(n ln n) .
О(n ln n)
= О(n ln n)
б) Визначення назви асимптотичного класу ефективності алгоритму.
О(n ln n) – Логаритмічний.
Результати виконання програми.
/
Висновки.
Виконавши дану лабораторну роботу я, вивчив і програмно реалізував метод сортування даних та дослідив їх ефективності.
Додатки (тексти програм з коментарями).
#include <iostream>
#include <vector>
using namespace std;
// Злиття двох впорядкованих масивiв
// m1 - Перший масив
// m2 - Другий масив
// l1 - Довжина 1-го масиву
// l2 - Довжина 2-го масиву
// Повертає злитий масив
int* HelpSort(int *m1, int* m2, int l1, int l2)
{
int* ret = new int[l1+l2];
int n = 0;
// зливаємо масиви поки один з них не закiнчиться
while (l1 && l2)
{
if (*m1 < *m2)
{
cout << "Запис елементу з 1-ї пiдпослiдовностi" << endl;
ret[n] = *m1;
m1++;
l1--;
}
else
{
cout << "Запис елементу з 2-ї пiдпослiдовностi" << endl;
ret[n] = *m2;
m2++;
l2--;
}
n++;
}
// Якщо закiнчився масив 1-й
if (l1 == 0)
{
for (int i=0; i<l2; i++)
{
cout << "Запис елементу з 2-ї пiдпослiдовностi" << endl;
ret[n++] = *m2++;
}
}
// Якщо закiнчився масив 2-й
else
{
for (int i=0; i<l1; i++)
{
cout << "Запис елементу з 1-ї пiдпослiдовностi" << endl;
ret[n++] = *m1++;
}
}
return ret;
}
// Функцiя злиття
void Sort(int * mas, const int len)
{
int n = 1, l, m;
int *mas1;
while (n < len)
{
l = 0;
while (l < len)
{
if (l+n >= len)
break;
m = (l+n*2>len) ? (len-(l+n)) : n; // вибiрка довжини пiдпослiдовностей
cout << "Довжина 1-ї пiдпослiдовностi: " << n << endl;
cout << "Довжина 2-ї пiдпослiдовностi: " << m << endl;
mas1 = HelpSort(mas + l, mas + l + n, n, m); // злиття цих пiдпослiдовностей
for (int i = 0; i<n+m; i++)
mas[l+i] = mas1[i]; // перезапис вiдсортованої посл.
delete [] mas1; // очищення пам"ятi
l += n*2;
for (unsigned k = 0; k < len; ++k)
cout << mas[k] << " ";
cout << endl;
}
n *= 2;
}
}
int main()
{
setlocale(0, "Ukr");
int n = 10;
vector<int> vct;
cout << "Enter array: ";
while (n != 0)
{
cin >> n;
vct.push_back(n);
}
int *arr = new int[vct.size()-1];
n = vct.size()-1;
for (unsigned i = 0; i < n; ++i)
{
arr[i] = vct[i];
cout << arr[i] << " ";
}
cout << endl;
Sort(arr, n);
for (unsigned i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << endl;
system("pause");
return 0;
}
25.01.2014 19:01-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора