Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Інститут комп’ютерних наук та інформаційних технологій
Факультет:
Не вказано
Кафедра:
Програмного забезпечення (ПЗ)
Інформація про роботу
Рік:
2007
Тип роботи:
Лабораторна робота
Предмет:
Алгоритми і структури даних
Група:
ПІ
Частина тексту файла (без зображень, графіків і формул):
Міністерство науки і освіти України.
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій.
Кафедра ПЗ
Звіт
До лабораторної роботи №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%
Оголошення від адміністратора