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