Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
DevioLab
CRYPTO TRADING AUTOMATION
LIVE
AUTOMATED CRYPTO TRADING • BINANCE
Автоматизуйте свій
криптопортфель
Торгові боти DevioLab аналізують крипторинок,
автоматично відкривають і закривають позиції
та керують вашим портфелем на Binance 24/7.
CRYPTO
80 Bots
BINANCE
Spot Trading
TRADING
24 / 7
deviolab.com
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
Не вказано
Кафедра:
Програмного забезпечення (ПЗ)
Інформація про роботу
Рік:
2015
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми і структури даних
Група:
ПІ
Частина тексту файла (без зображень, графіків і формул):
Міністерство науки і освіти України.
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій.
Кафедра ПЗ
Звіт
До лабораторної роботи №2
За курсом «Алгоритми і структури даних».
Виконав
студент групи ПІ 1
Львів 2007
Тема роботи: Ознайомлення із методами сортування. Алгоритм вибірки.
Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із методом сортування вибірки. Виконати лабораторну роботу використавши здобуті знання по методам сортування, зокрема по методу вибірки.
1. ТЕОРЕТИЧНІ ВІДОМОСТІ
Будуватимемо готову послідовність, починаючи з лівого кінця масиву. Алгоритм складається з n послідовних кроків, починаючи від нульового і закінчуючи (n-1) -м.
На i-м кроці вибираємо найменший з елементів а[i]... а[n] і міняємо його місцями з а[i]. Послідовність кроків при n=5 зображена на малюнку нижче.
Для знаходження найменшого елементу з n+1 розглянутий алгоритм здійснює n порівнянь. З урахуванням того, що кількість елементів, що розглядаються на черговому кроці, зменшується на одиницю, загальну кількість операцій:
n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n ) = Theta(n2).
Завдання:
Впорядкувати одновимірний масив методом вибірки. Повторити декілька раз з різною кількістю елементів та порівняти час виконання.
Код програми
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<conio.h>
void vstavka (int N[], int d)
{
int k,l,r,tmp;
for (k=0;k<d-1;k++)
{ r=k; tmp=N[k];
for (l=k+1;l<d;l++)
if (N[l]<tmp)
{
r=l;
tmp=N[l];
}
N[r]=N[k];
N[k]=tmp;
}
}
int verify(int N[], int d)
{
int k;
for (k=0;k<d-1;k++)
if (N[k]>N[k+1])
return 0;
return 1;
}
void main(void)
{
int N[100000],M[100000];
int i,j,m;
int C[5]={10000,20000,50000,80000,100000};
clock_t start, end;
clrscr();
for (i=0;i<5;i++)
{
for (j=0;j<C[i];j++)
N[j]=rand();
start=clock();
vstavka(N, C[i]);
end=clock();
break;
printf ("%d - %.3f - %s\n", C[i], (end-start)/CLK_TCK, verify(N, C[i]) ? "OK" : "Error");
}
getch();
}
Протокол роботи програми:
Висновок: алгоритм сортування вибіркою значно швидший за бульбашковий, тому що не використовує додаткової пам'яті, а всі операції відбуваються "на місці".
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора