Алгоритми і структури даних. Звіт до лабораторної роботи з Інформаційні технології. Робота № 518979

Алгоритми і структури даних

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

Не вказано

Кафедра:

Не вказано

Інформація про роботу

Рік:

2013

Тип роботи:

Звіт до лабораторної роботи

Предмет:

Інформаційні технології

Група:

ПІ-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(); } Протокол роботи програми: Висновок: алгоритм сортування вибіркою значно швидший за бульбашковий, тому що не використовує додаткової пам'яті, а всі операції відбуваються "на місці".

Звіт до лабораторної роботи Інформаційні технології

infoman

28.01.2013 14:21

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись