Serwis Edukacyjny w I-LO w Tarnowie Materiały dla uczniów liceum |
Wyjście Spis treści Wstecz Dalej
Autor artykułu: mgr Jerzy Wałaszek |
©2024 mgr Jerzy Wałaszek |
Podany w poprzednim rozdziale algorytm sortowania bąbelkowego można zoptymalizować pod względem czasu wykonania. Jeśli przyjrzymy się dokładnie obiegom wykonywanym w tym algorytmie, to zauważymy bardzo istotną rzecz:
Po wykonaniu pełnego obiegu w algorytmie sortowania bąbelkowego najstarszy element wyznaczony przez przyjęty porządek zostaje umieszczony na swoim właściwym miejscu - na końcu zbioru. |
Wniosek ten jest oczywisty. W każdej kolejnej parze porównywanych elementów element starszy przechodzi na drugą pozycję. W kolejnej parze jest on na pierwszej pozycji, a skoro jest najstarszym, to po porównaniu znów przejdzie na pozycję drugą itd. - jest jakby ciągnięty na koniec zbioru (jak bąbelek powietrza wypływający na powierzchnię wody).
Przykład:
Wykonamy jeden obieg sortujący dla zbioru pięcioelementowego
Obieg | Zbiór | Opis operacji |
1 |
9 3 1 7 0
|
Para wymaga przestawienia elementów. Element najstarszy przejdzie na drugą pozycję w parze. |
3 9 1 7 0 |
Konieczne przestawienie elementów. Element najstarszy znów trafi na pozycję drugą w parze. | |
3 1 9 7 0 |
Konieczne przestawienie elementów. | |
3 1 7 9 0
|
Ostatnia para również wymaga przestawienia elementów. | |
3 1 7 0 9
|
Koniec obiegu. Najstarszy element znalazł się na końcu zbioru. |
Co z tego wynika dla nas? Otóż po każdym obiegu na końcu zbioru tworzy się podzbiór uporządkowanych najstarszych elementów. Zatem w kolejnych obiegach możemy pomijać sprawdzanie ostatnich elementów - liczebność zbioru do posortowania z każdym obiegiem maleje o 1.
Przykład:
Dokończmy sortowania podanego powyżej zbioru uwzględniając podane przez nas fakty. Po pierwszym obiegu na końcu zbioru mamy umieszczony element najstarszy. W drugim obiegu będziemy zatem sortować zbiór 4 elementowy, w trzecim obiegu 3 elementowy i w obiegu ostatnim, czwartym - zbiór 2 elementowy.
Obieg | Zbiór | Opis operacji |
2 |
3 1 7 0 9 |
Para wymaga przestawienia elementów. |
1 3 7 0 9 |
Dobra kolejność | |
1 3 7 0 9 |
Konieczne przestawienie elementów. | |
1 3 0 7 9
|
Koniec obiegu. Na końcu zbioru mamy 2 elementy uporządkowane. | |
3 |
1 3 0 7 9 |
Dobra kolejność |
1 3 0 7 9 |
Konieczne przestawienie elementów. | |
1 0 3 7 9
|
Koniec obiegu. Na końcu zbioru mamy 3 elementy uporządkowane. | |
4 |
1 0 3 7 9 |
Konieczne przestawienie elementów. |
0 1 3 7 9 |
Koniec ostatniego obiegu - zbiór jest posortowany. |
W porównaniu do tabelki z poprzedniego rozdziału nawet wzrokowo możemy zauważyć istotne zmniejszenie ilości niezbędnych operacji.
n | - liczba elementów w sortowanym zbiorze, n ∈ N |
d[ ] | - zbiór n-elementowy, który będzie sortowany. Elementy zbioru mają indeksy od 1 do n. |
d[ ] | - posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n. |
i, j | - zmienne sterujące pętli, i, j ∈ N |
K01: | Dla j = n - 1, n - 2, ..., 1: Wykonuj krok K02 |
K02: | Dla i = 1, 2, ..., j: jeśli d[i] > d[i + 1], to d[i] ↔ d[i + 1] |
K03: | Zakończ |
Zmiany w stosunku do poprzedniej wersji zaznaczyliśmy na schemacie blokowym innym kolorem elementów. Są one następujące:
Pozostała część algorytmu nie jest zmieniona - w pętli wewnętrznej nr 2
sprawdzamy, czy element
Ilość obiegów pętli wewnętrznej wynosi:
Otrzymane wyrażenie ma wciąż kwadratową klasę złożoności obliczeniowej,
jednakże
C++// Sortowanie Bąbelkowe - Wersja nr 2 //-------------------------------------------------------- // (C)2012 mgr Jerzy Wałaszek // I Liceum Ogólnokształcące // im. K. Brodzińskiego // w Tarnowie //-------------------------------------------------------- #include <cmath> #include <iostream> #include <iomanip> #include <cstdlib> #include <time.h> using namespace std; const int N = 20; // Liczebność zbioru. // Program główny //--------------- int main() { int d[N],i,j; cout << " Sortowanie babelkowe\n" " WERSJA NR 2\n" "----------------------\n" "(C)2005 Jerzy Walaszek\n\n" "Przed sortowaniem:\n\n"; // Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi // a następnie wyświetlamy jej zawartość srand((unsigned)time(NULL)); for(i = 0; i < N; i++) d[i] = rand() % 100; for(i = 0; i < N; i++) cout << setw(4) << d[i]; cout << endl; // Sortujemy for(j = N - 1; j > 0; j--) for(i = 0; i < j; i++) if(d[i] > d[i + 1]) swap(d[i], d[i + 1]); // Wyświetlamy wynik sortowania cout << "Po sortowaniu:\n\n"; for(i = 0; i < N; i++) cout << setw(4) << d[i]; cout << endl; return 0; } |
Pascal// Sortowanie Bąbelkowe - Wersja nr 2 //-------------------------------------------------------- // (C)2012 mgr Jerzy Wałaszek // I Liceum Ogólnokształcące // im. K. Brodzińskiego // w Tarnowie //-------------------------------------------------------- program Bubble_Sort_2; const N = 20; // Liczebność zbioru. var d : array[1..N] of integer; // Program główny //--------------- var i,j,x : integer; begin writeln(' Sortowanie babelkowe '); writeln(' WERSJA NR 2 '); writeln('----------------------'); writeln('(C)2005 Jerzy Walaszek'); writeln; // Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi // a następnie wyświetlamy jej zawartość randomize; for i := 1 to N do d[i] := random(100); writeln('Przed sortowaniem:'); writeln; for i := 1 to N do write(d[i] : 4); writeln; // Sortujemy for j := N - 1 downto 1 do for i := 1 to j do if d[i] > d[i+1] then begin x := d[i]; d[i] := d[i+1]; d[i+1] := x; end; // Wyświetlamy wynik sortowania writeln('Po sortowaniu:'); writeln; for i := 1 to N do write(d[i] : 4); writeln; writeln('Nacisnij Enter...'); readln; end. |
Basic' Sortowanie Bąbelkowe - Wersja nr 2 '-------------------------------------------------------- ' (C)2012 mgr Jerzy Wałaszek ' I Liceum Ogólnokształcące ' im. K. Brodzińskiego ' w Tarnowie '-------------------------------------------------------- OPTION EXPLICIT CONST N = 20 ' Liczebność zbioru. DIM d(1 TO N) AS INTEGER, i AS INTEGER, j AS INTEGER PRINT " Sortowanie babelkowe " PRINT " WERSJA NR 2 " PRINT "----------------------" PRINT "(C)2005 Jerzy Walaszek" PRINT ' Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi ' a następnie wyświetlamy jej zawartość RANDOMIZE TIMER FOR i = 1 TO N: d(i) = INT(RND * 100): NEXT PRINT "Przed sortowaniem:" PRINT FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT PRINT ' Sortujemy FOR j = N - 1 TO 1 STEP -1 FOR i = 1 TO j IF d(i) > d(i+1) THEN SWAP d(i), d(i+1) NEXT NEXT ' Wyświetlamy wynik sortowania PRINT "Po sortowaniu:" PRINT FOR i = 1 TO N: PRINT USING "####"; d(i);: NEXT PRINT PRINT "Nacisnij Enter..." SLEEP END |
JavaScript<html> <head> </head> <body> <form style="BORDER-RIGHT: #ff9933 1px outset; PADDING-RIGHT: 4px; BORDER-TOP: #ff9933 1px outset; PADDING-LEFT: 4px; PADDING-BOTTOM: 1px; BORDER-LEFT: #ff9933 1px outset; PADDING-TOP: 1px; BORDER-BOTTOM: #ff9933 1px outset; BACKGROUND-COLOR: #ffcc66" name="frmbubblesort"> <h3 style="text-align: center">Sortowanie Bąbelkowe - wersja nr 2</h3> <p style="TEXT-ALIGN: center"> (C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie </p> <hr> <p style="TEXT-ALIGN: center"> <input onclick="main()" type="button" value="Sortuj" name="B1"> </p> <p id="t_out" style="TEXT-ALIGN: center">...</p> </form> <script language=javascript> // Sortowanie Bąbelkowe - wersja nr 2 //-------------------------------------------------------- // (C)2012 mgr Jerzy Wałaszek // I Liceum Ogólnokształcące // im. K. Brodzińskiego // w Tarnowie //-------------------------------------------------------- var N = 20; // Liczebność zbioru. function main() { var d = new Array(N); var i,j,x,t; // Najpierw wypełniamy tablicę d[] liczbami pseudolosowymi for(i = 0; i < N; i++) d[i] = Math.floor(Math.random() * 100); t = "Przed sortowaniem:<BR><BR>"; for(i = 0; i < N; i++) t += d[i] + " "; t += "<BR><BR>"; // Sortujemy for(j = N - 1; j > 0; j--) for(i = 0; i < j; i++) if(d[i] > d[i + 1]) { x = d[i]; d[i] = d[i + 1]; d[i + 1] = x; }; // Wyświetlamy wynik sortowania t += "Po sortowaniu:<BR><BR>"; for(i = 0; i < N; i++) t += d[i] + " "; document.getElementById("t_out").innerHTML = t; } </script> </body> </html> |
Wynik: |
Sortowanie babelkowe WERSJA NR 2 ---------------------- (C)2005 Jerzy Walaszek Przed sortowaniem: 44 29 43 80 95 88 40 45 28 13 8 90 49 28 76 64 22 70 4 6 Po sortowaniu: 4 6 8 13 22 28 28 29 40 43 44 45 49 64 70 76 80 88 90 95 |
W celach badawczych testujemy czas wykonania algorytmu sortowania bąbelkowego 2 w środowisku opisanym we wstępie. Program testujący jest następujący:
Pascal// Program testujący czas sortowania dla // danego algorytmu sortującego //-------------------------------------- // (C)2012 mgr Jerzy Wałaszek // I Liceum Ogólnokształcące // w Tarnowie //-------------------------------------- program TestCzasuSortowania; uses Windows; const NAZWA = 'Sortowanie bąbelkowe - Bubble Sort 2'; K1 = '--------------------------------------------------'; K2 = '(C)2011/2012 I Liceum Ogolnoksztalcace w Tarnowie'; K3 = '------n---------tpo---------tod---------tpp---------tpk---------tnp'; K4 = '-------------------------------------------------------------------'; MAX_LN = 5; // określa ostatnie LN LN : array[1..8] of integer = (1000,2000,4000,8000,16000,32000,64000,128000); var d : array[1..128000] of real; // sortowana tablica n : integer; // liczba elementów qpf,tqpc : int64; // dane dla pomiaru czasu qpc1,qpc2 : int64; // Tutaj umieszczamy procedurę sortującą tablicę d //------------------------------------------------------- function Sort : extended; var i,j : integer; x : real; begin QueryPerformanceCounter(addr(qpc1)); for j := n - 1 downto 1 do for i := 1 to j do if d[i] > d[i+1] then begin x := d[i]; d[i] := d[i+1]; d[i+1] := x; end; QueryPerformanceCounter(addr(qpc2)); Sort := (qpc2 - qpc1 - tqpc) / qpf; end; // Program główny //--------------- var i,j,k : integer; tpo,tod,tpp,tpk,tnp : extended; f : Text; begin if QueryPerformanceFrequency(addr(qpf)) then begin QueryPerformanceCounter(addr(qpc1)); QueryPerformanceCounter(addr(qpc2)); tqpc := qpc2 - qpc1; assignfile(f,'wyniki.txt'); rewrite(f); // Wydruk na ekran writeln('Nazwa: ',NAZWA); writeln(K1); writeln(K2); writeln; writeln(K3); // Wydruk do pliku writeln(f,'Nazwa: ',NAZWA); writeln(f,K1); writeln(f,K2); writeln(f,''); writeln(f,K3); for i := 1 to MAX_LN do begin n := LN[i]; // Czas sortowania zbioru posortowanego for j := 1 to n do d[j] := j; tpo := Sort; // Czas sortowania zbioru posortowanego odwrotnie for j := 1 to n do d[j] := n - j; tod := Sort; // Czas sortowania zbioru posortowanego // z przypadkowym elementem na początku - średnia z 10 obiegów tpp := 0; for j := 1 to 10 do begin for k := 1 to n do d[k] := k; d[1] := random * n + 1; tpp += Sort; end; tpp /= 10; // Czas sortowania zbioru posortowanego // z przypadkowym elementem na końcu - średnia z 10 obiegów tpk := 0; for j := 1 to 10 do begin for k := 1 to n do d[k] := k; d[n] := random * n + 1; tpk += Sort; end; tpk /= 10; // Czas sortowania zbioru nieuporządkowanego - średnia z 10 obiegów tnp := 0; for j := 1 to 10 do begin for k := 1 to n do d[k] := random; tnp += Sort; end; tnp /= 10; writeln(n:7,tpo:12:6,tod:12:6,tpp:12:6,tpk:12:6,tnp:12:6); writeln(f,n:7,tpo:12:6,tod:12:6,tpp:12:6,tpk:12:6,tnp:12:6); end; writeln(K4); writeln(f,K4); writeln(f,'Koniec'); closefile(f); writeln; writeln('Koniec. Wyniki w pliku WYNIKI.TXT'); end else writeln('Na tym komputerze program testowy nie pracuje !'); writeln; write('Nacisnij klawisz ENTER...'); readln; end. |
Otrzymane wyniki są następujące (dla komputera o innych parametrach wyniki mogą się różnić co do wartości czasów wykonania, dlatego w celach porównawczych proponuję uruchomić podany program na komputerze czytelnika):
Zawartość pliku wygenerowanego przez program | ||||||||||||||||||
Nazwa: Sortowanie bąbelkowe - Bubble Sort 2 Objaśnienia oznaczeń (wszystkie czasy podano w sekundach):
|
(Arkusz kalkulacyjny Excel do
wyznaczania klasy czasowej złożoności obliczeniowej)
(Arkusz kalkulacyjny Excel do
wyznaczania wzrostu prędkości sortowania)
Analizując wyniki obliczeń w arkuszu kalkulacyjnym otrzymanych czasów
sortowania dla algorytmu sortowania bąbelkowego 2 wyciągamy następujące wnioski:
Cechy
Algorytmu Sortowania Bąbelkowego wersja nr 2 |
|
klasa złożoności obliczeniowej optymistyczna | |
klasa złożoności obliczeniowej typowa | |
klasa złożoności obliczeniowej pesymistyczna | |
Sortowanie w miejscu | TAK |
Stabilność | TAK |
Klasy złożoności obliczeniowej szacujemy następująco:
Własności algorytmu | |||||
Algorytm | tpo | tod | tpp | tpk | tnp |
Sortowanie bąbelkowe wersja nr 2 |
|||||
Wzrost prędkości sortowania | |||||
Algorytmy | tpo | tod | tpp | tpk | tnp |
Sortowanie
bąbelkowe 1 Sortowanie bąbelkowe 2 |
|||||
dobrze | niewiele | dobrze | dobrze | niewiele |
Zobacz również na: Wersję 1 | Wersję 3 | Wersję 4 | Dwukierunkowe sortowanie bąbelkowe
Zespół Przedmiotowy Chemii-Fizyki-Informatyki w I Liceum Ogólnokształcącym im. Kazimierza Brodzińskiego w Tarnowie ul. Piłsudskiego 4 ©2024 mgr Jerzy Wałaszek |
Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email:
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.