![]() |
Wyjście Spis treści Poprzedni Następny
Autor artykułu: mgr Jerzy Wałaszek, Wersja 4.1 |
©2011 mgr Jerzy Wałaszek |
Podrozdziały | Tematy pokrewne | ||
Algorytm sortowania bąbelkowego wykonuje dwa rodzaje operacji:
- test bez zamiany miejsc elementów
- test ze zamianą miejsc elementów.
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
![]() |
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
![]() |
K01: | Dla j = n - 1, n - 2, ..., 1: wykonuj 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 |
Efekt uruchomienia programu |
---|
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 |
DevPascal |
// 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. |
---|---|
Code::Blocks |
// 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; } |
Free 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> |
Tutaj możesz przetestować działanie prezentowanego skryptu:
|
W celach badawczych testujemy czas wykonania algorytmu sortowania bąbelkowego 3 w środowisku opisanym we wstępie. Program testujący jest następujący:
DevPascal |
// 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 | O(n) -O(n2) |
klasa złożoności obliczeniowej typowa | O(n2) |
klasa złożoności obliczeniowej pesymistyczna | O(n2) |
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 |
O(n) | O(n2) | O(n) | O(n2) | O(n2) | |||
tpo << tod | tpp << tpk |
|
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
W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.
![]() | I Liceum Ogólnokształcące |