Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лабораторна робота №5
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
УІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2012
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми та методи обчислень
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
національний університет “Львівська політехніка”
Лабораторна робота № 5
"Розробка та дослідження ефективності методів сортування"
№ варіанта = [(місяць народження) + (ASCII–код другої літери прізвища – мала латинська літера)] % 30 + 1=
=( 8 + 115)%30 + 1 =123%30 + 1= 3+1=4
Львів – 2012
1. МЕТА РОБОТИ
Вивчення, реалізація та дослідження ефективності методів сортування даних.
ЗАВДАННЯ НА ЛАБОРАТОРНУ РОБОТУ
Задати послідовність цілих чисел довільної довжини і представити її у пам’яті комп’ютера у вигляді масиву або лінійного зв’язаного списку. Програмно реалізувати один із вказаних нижче методів сортування згідно з варіантом. Під час виконання програми обов’язково виводити на екран монітора всі проміжні кроки процесу сортування.
Провести дослідження побудованого методу за такою схемою:
1). Обґрунтувати вибір структури даних, в якій має зберігатись інформація (масив чи список; якщо список, то однозв’язаний чи двозв’язаний).
2). Намалювати схему алгоритму на прикладі послідовності з десяти (або більше при необхідності) цілих чисел, показуючи всі проміжні кроки процесу сортування.
3). Дослідити метод cортування на стійкість.
4). Дослідити метод cортування на економність використання пам’яті.
5). Дослідити метод на можливу специфіку вхідної послідовності (чи може послідовність містити елементи з однаковими ключами, чи має бути вхідна послідовність частково відсортована, чи мають елементи послідовності знаходитись у певному діапазоні і т.п.).
6). Дослідити ефективність методу. Для цього визначити значення кількості порівнянь (С) і кількості перестановок (М) в найкращому () і в найгіршому () випадках. Середні значення кількості порівнянь () і кількості перестановок () визначити, як середнє арифметичне для кожної величини від великої кількості спроб сортування випадкових послідовностей.
Визначити до якого класу (підкласу) належить досліджуваний метод. Використовуючи методику аналізу основних алгоритмічних конструкцій та визначення набору "елементарних" операцій, обчислити складність методу, що характеризується функцією трудомісткості. Зробити висновки про ефективність методу.
№ варіанта 4. Сортування методом підрахунку порівнянь [1, 94-97 c.]
3. Опис алгоритму сортування
Сортування шляхом пiдрахунку. Кожен елемент порiвнюється з усiма iншими; кiнцевце положення елемента визначається пiсля пiдрахунку числа меньших ключiв.
Цей простий метод заснований на тому, що j-й ключ в кiнцевiй впорядкованiй послiдовностi перевищуєрiвно ] —1 решти ключiв.По-iншому, якщо вiдомо, що деякий ключ перевищуєрiвно 27 iнших i якщо нiякi два ключа не рiвнi, то пiсля cортування вiдповiдний за пис має зайняти 28-е мiсце. Таким чином, iдея полягає в тому, щоб порiвняти попарно всi ключi i пiдрахувати, скiльки з них менше кожного окремого ключа. Очевидний спосiб виконання поставленної задачi такий:
((порiвняти Кi с Кj) при 1 < j < N) при I < i < N;
Бiльше половини цих операцiй зайвi, оскiльки не треба порiвнювати ключ сам з собою i пiсля порiвняння Кa з Кb вже не треба порiвнювати Кb з Кa.Тому достатньо
((порiвняти Кi с Кj) при 1 <= j< i) при 1 < i<= N. Дiстаємо наступний алгоритм.
Алгоритм .Цей алгоритм сортує записи R1,...,Rn по ключах К1,..., .Кn, використовуючи допомiжну таблицю COUNT[1], ..., COUNT[N] для пiдрахунку числа ключiв, меньших вiд данного.Пiсля завершення алгоритму величина COUNT[j] -1 визначає кiнцеве положення запису Rj.
С1. [скинути лiчильники СОUNT.] Встановити в лiчильниках COUNT[1] - СОUNT [N] нулi.
С2. [Цикл по i.] виконати крок СЗ при j = N, N—1, ..., 2 потiм завершує виконання процедури.
СЗ. [Цикл по j.] виконати крок С4 при j = i-1, i-2, ..., 1.
С4. [порiвняти Кi : Kj.] якщо Кi < Кj, то збiльшити СOUNT[j] на 1; в протилежному випадку збiльшити COUNT[i] на 1.
В данному алгоритмi записи не перемiщуються, оскiльки таблиця СOUNT визначає кiнцеве положення записiв - вказує, куди треба переслати запис Rj, а не запис, який треба переслати на мiсце Rj.
4.Результати виконання програми.
5.Дослідження методу.
Обґрунтування вибору структури даних.
Цей алгоритм сортує записи R1,...,Rn по ключах К1,..., .Кn, використовуючи допомiжну таблицю COUNT[1], ..., COUNT[N] для пiдрахунку числа ключiв, меньших вiд данного.Пiсля завершення алгоритму величина COUNT[j] -1 визначає кiнцеве положення запису Rj. записи не перемiщуються, оскiльки таблиця СOUNT визначає кiнцеве положення записiв - вказує, куди треба переслати запис Rj, а не запис, який треба переслати на мiсце Rj.Оскiльки самi данi не перемiщуються - вибiр структури даних не має особливого значення, тому для демонстрацi методу простiше вибрати масив довiльних цiлих чисел, значення яких взяти за ключi.
5.3Дослідження на стійкість.
5.2 Схема алгоритму cортування.
5.4Дослідження на економність використання пам’яті.
Цей алгоритм використовуює допомiжну таблицю COUNT[1], ..., COUNT[N] для пiдрахунку числа ключiв, меньших вiд данного — тому потрiбно використати додаткову память для розмiщення цiєї допомiжної таблицi Пiсля завершення алгоритму величина COUNT[j] -1 визначає кiнцеве положення запису Rj. Записи не перемiщуються, оскiльки таблиця СOUNT визначає кiнцеве положення записiв - вказує, куди треба переслати запис Rj, а не запис, який треба переслати на мiсце Rj.
5.5Дослідження на специфіку вхідної послідовності.
Алгоритм С дає вiрний результат незалежно вiд числа рiвних ключiв i неефективний при великому N;
5.6Дослідження ефективності методу.
а) Кількість порівнянь в найкращому, в найгіршому та в середньому випадках.
Цей метод потребує порiвняння всiх пар ключiв (Кi,Кj) в будь-якому випадку.
б) Кількість перестановок в найкращому, в найгіршому та в середньому випадках.
В данному алгоритмi записи не перемiщуються, оскiльки таблиця СOUNT визначає кiнцеве положення записiв - вказує, куди треба переслати запис Rj, а не запис, який треба переслати на мiсце Rj.
в) Визначення класу (підкласу) до якого належить досліджуваний алгоритм.
3.1. Підклас NPRL (Low) – підклас алгоритмів, трудомісткость яких слабо залежить від параметричної складової.
g+(n)=O(fn (n)) <=> g*(n)= Ө(1).
До цього підкласу відноситься, наприклад, алгоритм пошуку максимального елемета в масиві, тому що кількість переприсвоювань максимуму в найгіршому випадку (коли масив відсортований по зростанню) має рівний порядок з оцінкою зовнішнього циклу для перебору n елементів.
г) Обчислення функції трудомісткості.
д) Висновок про ефективність методу
Даний алгоритм неефективний при великих значеннях N ,при збiльшеннi N в два рази- час роботи збiльшиться в чотири рази, але даний алгоритм цiкавий своєю простотою, а не ефективнстю.
Додаток
#include<stdio.h>
#include<conio.h>
#include<iostream>
using namespace std;
int main()
{
int i,j,n;
int count[10]={0};
int arr[10]={89,23,65,8,90,76,32,45,21,33};
cout << "masuv: ";
for(i=0;i<10;i++){
cout.width(5);
cout <<arr[i];
}
cout<<"\ncount(poch.): ";
for(i=0;i<10;i++){
cout.width(5);
cout <<count[i];
}
cout <<"\n";
for(i=10;i>=1;i--){
for(j=i-1;j>=0;j--){
if(arr[i]<=arr[j]){
count[j]++;}
else {count[i]++;}
}
cout<<"count(i=";
cout.width(2);
cout<<i<<"): ";
for(n=0;n<10;n++){
cout.width(5);
cout <<count[n];}
cout<<"\n";
}
getch();
return 0;
}
19.12.2013 23:12-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора