Міністерство науки і освіти України. Національний університет “Львівська політехніка” Інститут комп’ютерних наук та інформаційних технологій. Кафедра ПЗ Звіт До лабораторної роботи №2 За курсом «Алгоритми і структури даних». Львів 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(); } Протокол роботи програми:
Висновок: алгоритм сортування вибіркою значно швидший за бульбашковий, тому що не використовує додаткової пам'яті, а всі операції відбуваються "на місці".