Міністерство науки і освіти України Національний університет “Львівська політехніка” Інститут комп’ютерних наук та інформаційних технологій кафедра програмного забезпечення Звіт з лабораторної роботи № 8 з дисципліни “Алгоритми і структури даних ” Львів 2008 Тема роботи: Ознайомлення із методами сортування. Алгоритм сортування на деревах. Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із методом сортування на деревах. Виконати лабораторну роботу використавши здобуті знання з методів сортування, зокрема методу сортування на деревах. ТЕОРЕТИЧНІ ВІДОМОСТІ Метод вибірки з дерева. Послідовність чисел розбивається на пари, які об‘єднуються за принципом «син-батько». Батьком з двох синів стає найбільше число. Процес повторюється, доки не буде виділене одне число, найбільше, яке стане корнем утвореного дерева. У разі відсутності одного числа, батьком стає єдиний нащадок (син). Число, що попало в корінь замінюється на безмежність. Процес повторюється для знаходження наступного найбільшого числа і т.д. З рис. 1 видно, що задана послідовність буде впорядкована у низхідному порядку за 10-1=9 кроків. Сумарний час виконання такого сортування приблизно пропорційний величині п log2 n . Існує декілька модифікацій цього алгоритму, які скорочують цей час.
Рис. 1. Схема сортування методом вибірки з дерева: а - послідовність з десяти чисел для відбору першого найбільшого елемента; б - вибір другого найбільшого елемента. Текст програми #include<stdio.h> #include<conio.h> #include<stdlib.h> #include<alloc.h> #define N 2000 struct S* create(int); struct S* create(struct S*, struct S*); void clean(struct S*); int min(int, int); /*-Struktura-*/ struct S { int a; //Vlasne znachenna struct S* left; //Vk. na livogo syna struct S* right; //Vk. na pravogo syna }; //----------------------------------- void main() { int rez=0; int mas[N],mas2[N]; /*-Inicializacija-*/ for (int i=0;i<N;i++) mas[i]=rand(); /*-Pobudova dereva-*/ for (int r=0;r<N;r++) { S* pmas[N]; //Vk. na vershyny int cnt=N; //Kilkist vershyn na rivni for(int i=0;i<N;i++) pmas[i]=create(mas[i]);//Budujemo riven structur while(cnt>1)//Do najvyschogo rivn'a { int j=0; //Perenesenna na vyschyj riven vershyny //z menshym znachennam for(int i=0;i<cnt;i+=2) pmas[j++]= i+1<cnt ? create(pmas[i],pmas[i+1]): pmas[i]; cnt=j; } //Perenosymo znachenna korenja //u zapasnyj masyv mas2[r]=pmas[0]->a; //Zamina znajdenogo elementa //u vyhidnomu masyvi for (int c=0;c<N;c++) if(mas[c]==pmas[0]->a) {mas[c]=32767; break;} /*-Ochyschenn'a pam'jati-*/ clean(pmas[0]); } /*-Perevirka-*/ for(int hi=0;i<N-1;i++) if (mas2[i]>mas2[i+1]) rez=1; if(rez==1) puts("Ne posortovano!"); else puts("Posortovano!"); } //------------------------------------ /*-Stvorenna vershyn nyzchogo rivn'a-*/ struct S* create(int a) { struct S* b=(struct S*)malloc(sizeof(struct S)); b->a=a; b->left=NULL; b->right=NULL; return b; } /*-Stvorenn'a vershyn vyschyh rivniv-*/ struct S* create(struct S* a, struct S* b) { struct S* c=(struct S*)malloc(sizeof(struct S)); c->left=a; c->right=b; c->a=min(a->a,b->a); return c; } /*-Ochyschenna pam'jati-*/ void clean(struct S* b) { if(b->left!=NULL) delete(b->left); if(b->right!=NULL) delete(b->right); free(b); } /*-Zn. minimal'nogo elementa-*/ int min(int a, int b) { return a<=b?a:b; } Протокол роботи програми