Міністерство науки і освіти України. Національний університет “Львівська політехніка” Інститут комп’ютерних наук та інформаційних технологій. Кафедра ПЗ Звіт До лабораторної роботи №1 За курсом «Алгоритми і структури даних». Львів 2007 Тема роботи: Ознайомлення із методами сортування. Алгоритм бульбашки. Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із Бульбашковим методом сортування. Виконати лабораторну роботу використавши здобуті знання по методам сортування, зокрема метод бульбашки. ТЕОРЕТИЧНІ ВІДОМОСТІ Розташуємо масив зверху вниз, від нульового елементу - до останнього. Ідея методу: крок сортування полягає в проході від низу до верху по масиву. По дорозі є видимими пари сусідніх елементів. Якщо елементи деякої пари знаходяться в неправильному порядку, то міняємо їх місцями.
Після нульового проходу по масиву "вгорі" виявляється "найлегший" елемент - звідси аналогія з бульбашкою. Наступний прохід робиться до другого зверху елементу, таким чином другий за величиною елемент піднімається на правильну позицію... Робимо проходи по нижній частині масиву, що все зменшується, до тих пір, поки в ній не залишиться тільки один елемент. На цьому сортування закінчується, оскільки послідовність впорядкована за збільшенням.
Середнє число порівнянь і обмінів мають квадратичний порядок зростання: Theta(n2), звідси і слідує, що алгоритм бульбашки дуже повільний і малоефективний. Завдання: Впорядкувати одновимірний масив методом бульбашки. Повторити декілька раз з різною кількістю елементів та порівняти час виконання. Код програми #include<stdio.h> #include<stdlib.h> #include<time.h> #include<conio.h> void bulbashka(int N[], int d) { int k,l,tmp; for (k=0;k<d-1;k++) for (l=0;l<d-k-1;l++) if (N[l+1]<N[l]) { tmp=N[l]; N[l]=N[l+1]; N[l+1]=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(); bulbashka(N, C[i]); end=clock(); break; printf ("%d - %.3f - %s\n", C[i], (end-start)/CLK_TCK, verify(N, C[i]) ? "OK" : "Error"); } getch(); } Протокол роботи програми:
Висновок: алгоритм сортування бульбашкою є одним з найпростіших методів, однак його алгоритмічна складність O(n2).