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 |
Algorytm sortowania bąbelkowego wykonuje dwa rodzaje operacji:
Pierwsza z tych operacji nie sortuje zbioru, jest więc operacją pustą. Druga operacja dokonuje faktycznej zmiany porządku elementów, jest zatem operacją sortującą.
Ze względu na przyjęty sposób sortowania algorytm bąbelkowy zawsze musi wykonać tyle samo operacji sortujących. Tego nie możemy zmienić. Jednakże możemy wpłynąć na eliminację operacji pustych. W ten sposób usprawnimy działanie algorytmu.
Jeśli dokładnie przyjrzałeś się wersjom 1 i 2, które prezentowaliśmy w poprzednich rozdziałach, to powinieneś dokonać następujących spostrzeżeń:
Możliwa jest dalsza redukcja operacji pustych, jeśli będziemy sprawdzać, czy w pętli wewnętrznej były przestawiane elementy (czyli czy wykonano operacje sortujące). Jeśli nie, to zbiór jest już posortowany (dlaczego?) i możemy zakończyć pracę algorytmu.
Teraz rośnie trudność wyznaczenia czasowej złożoności
obliczeniowej, ponieważ ilość faktycznie wykonywanych operacji porównań i
przestawień zależy od rozkładu elementów w sortowanym zbiorze. Zadanie
komplikuje dodatkowo fakt, iż operacja pusta jest zwykle wykonywana kilkakrotnie
szybciej od operacji sortującej. Na pewno można powiedzieć, iż dla zbioru
posortowanego algorytm wykona tylko
Przykład:
Posortujmy zbiór
Obieg | Zbiór | Opis operacji |
1 |
3 1 0 7 9 |
Konieczne przestawienie elementów |
1 3 0 7 9
|
Konieczne przestawienie elementów | |
1 0 3 7 9
|
Elementy w dobrej kolejności | |
1 0 3 7 9
|
Elementy w dobrej kolejności | |
1 0 3 7 9
|
Koniec pierwszego obiegu. Ponieważ były przestawienia elementów, sortowanie kontynuujemy | |
2 |
1 0 3 7 9 |
Konieczne przestawienie elementów |
0 1 3 7 9 |
Elementy w dobrej kolejności | |
0 1 3 7 9 |
Elementy w dobrej kolejności | |
0 1 3 7 9
|
Koniec drugiego obiegu. Było przestawienie elementów, zatem sortowanie kontynuujemy | |
3 |
0 1 3 7 9 |
Elementy w dobrej kolejności |
0 1 3 7 9 |
Elementy w dobrej kolejności | |
0 1 3 7 9
|
Koniec trzeciego obiegu. Nie było przestawień elementów, kończymy sortowanie. Wykonaliśmy o 1 obieg sortujący mniej. |
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 |
p | - znacznik zamiany miejsc elementów w zbiorze. p ∈ N |
K01: | Dla j = n - 1, n - 2, ..., 1: Wykonuj kroki K02...K04 |
K02: | p ← 1 |
K03: | Dla i = 1, 2, ..., j: Jeśli d[i] > d[i + 1], to d[i] ↔ d[i + 1]; p ← 0 |
K04: | Jeśli p = 1, to zakończ |
K05: | Zakończ |
Wprowadzona do algorytmu sortowania bąbelkowego modyfikacja ma na celu wykrycie posortowania zbioru. Zmiany zaznaczyliśmy blokami o odmiennym kolorze.
Zbiór będzie posortowany, jeśli po wykonaniu wewnętrznego obiegu sortującego nie wystąpi ani jedno przestawienie elementów porządkowanego zbioru.
Przed wejściem do pętli sortującej nr 2 ustawiamy zmienną pomocniczą p. Jeśli w pętli zajdzie potrzeba przestawienia elementów, to zmienna p jest zerowana. Po wykonaniu pętli sortującej sprawdzamy, czy zmienna p jest ustawiona. Jeśli tak, to przestawienie elementów nie wystąpiło, zatem kończymy algorytm. W przeciwnym razie wykonujemy kolejny obieg pętli nr 1.
Uwaga techniczna:
Zmienna
p powinna być typu liczbowego integer, a nie
boolean (chociaż tak może wydawać się właściwiej). Jednakże musimy
pamiętać, iż procesory Pentium są zoptymalizowane na liczby |
C++// Sortowanie Bąbelkowe - Wersja nr 3 //-------------------------------------------------------- // (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,p; cout << " Sortowanie babelkowe\n" " WERSJA NR 3\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--) { p = 1; for(i = 0; i < j; i++) if(d[i] > d[i + 1]) { swap(d[i], d[i + 1]); p = 0; } if(p) break; } // 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 3 //-------------------------------------------------------- // (C)2012 mgr Jerzy Wałaszek // I Liceum Ogólnokształcące // im. K. Brodzińskiego // w Tarnowie //-------------------------------------------------------- program Bubble_Sort_3; const N = 20; // Liczebność zbioru. var d : array[1..N] of integer; // Program główny //--------------- var i,j,p,x : integer; begin writeln(' Sortowanie babelkowe '); writeln(' WERSJA NR 3 '); 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 begin p := 1; 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; p := 0; end; if p = 1 then break; 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 3 '-------------------------------------------------------- ' (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, p AS INTEGER PRINT " Sortowanie babelkowe " PRINT " WERSJA NR 3 " 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 p = 1 FOR i = 1 TO j IF d(i) > d(i+1) THEN SWAP d(i), d(i+1) p = 0 END IF NEXT IF p = 1 THEN EXIT FOR 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 3</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 3 //-------------------------------------------------------- // (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,p,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--) { p = 1; for(i = 0; i < j; i++) if(d[i] > d[i + 1]) { x = d[i]; d[i] = d[i + 1]; d[i + 1] = x; p = 0; } if(p) break; } // 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 3 ---------------------- (C)2005 Jerzy Walaszek Przed sortowaniem: 31 17 26 0 42 61 24 89 56 72 92 66 91 13 74 88 10 90 68 25 Po sortowaniu: 0 10 13 17 24 25 26 31 42 56 61 66 68 72 74 88 89 90 91 92 |
W celach badawczych testujemy czas wykonania algorytmu sortowania bąbelkowego 3 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 3'; K1 = '--------------------------------------------------'; K2 = '(C)2011/2012 I Liceum Ogolnoksztalcace w Tarnowie'; K3 = '------n---------tpo---------tod---------tpp---------tpk---------tnp'; K4 = '-------------------------------------------------------------------'; MAX_LN = 6; // 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,p : integer; x : real; begin QueryPerformanceCounter(addr(qpc1)); for j := n - 1 downto 1 do begin p := 1; 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; p := 0; end; if p = 1 then break; 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 3 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 3 wyciągamy następujące wnioski:
Cechy
Algorytmu Sortowania Bąbelkowego wersja nr 3 |
|
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 3 |
|||||
Wzrost prędkości sortowania | |||||
Algorytmy | tpo | tod | tpp | tpk | tnp |
Sortowanie
bąbelkowe 2 Sortowanie bąbelkowe 3 |
|||||
dobrze | brak | dobrze | dobrze | brak |
Zobacz również na: Wersję 1 | Wersję 2 | 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.