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 |
Dwukierunkowe sortowanie bąbelkowe oparte jest na spostrzeżeniu, iż każdy obieg wewnętrznej pętli sortującej umieszcza na właściwym miejscu element najstarszy, a elementy młodsze przesuwa o 1 pozycję w kierunku początku zbioru. Jeśli pętla ta zostanie wykonana w kierunku odwrotnym, to wtedy najmłodszy element znajdzie się na swoim właściwym miejscu, a elementy starszy przesuną się o jedną pozycję w kierunku końca zbioru. Połączmy te dwie pętle sortując wewnętrznie naprzemiennie w kierunku normalnym i odwrotnym, a otrzymamy algorytm dwukierunkowego sortowania bąbelkowego.
Wykonanie pętli sortującej w normalnym kierunku ustali maksymalną pozycję w zbiorze, od której powinna rozpocząć sortowanie pętla odwrotna. Ta z kolei ustali minimalną pozycję w zbiorze, od której powinna rozpocząć sortowanie pętla normalna w następnym obiegu pętli zewnętrznej. Sortowanie możemy zakończyć, jeśli nie wystąpiła potrzeba zamiany elementów w żadnej z tych dwóch pętli.
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 | - zmienna sterująca pętli, i ∈ N |
pmin | - dolna granica pozycji sortowanych elementów, pmin ∈ N |
pmax | - górna granica pozycji sortowanych elementów, pmax ∈ N |
p | - numer pozycji zamiany elementów, p ∈ N |
K01: | Jeśli d[i] ≤ d[i
+ 1], to zakończ operację sortującą |
K02: | d[i] ↔ d[i + 1] |
K03: | p ← i |
K04: | Zakończ operację sortującą |
K01: | pmin ← 1; pmax ← n - 1 |
K02: | p ← 0 |
K03: | Dla i = pmin,
pmin
+ 1, ..., pmax: wykonuj operację sortującą |
K04: | Jeśli p = 0, to zakończ |
K05: | pmax ← p - 1; p ← 0 |
K06: | Dla i = pmax,
pmax
- 1, ..., pmin: wykonuj operację sortującą |
K07: | pmin ← p + 1 |
K08: | Jeśli p > 0, to idź do kroku K02 |
K09: | Zakończ |
W algorytmie wydzieliliśmy powtarzający się fragment operacji i nazwaliśmy go operacją sortującą. Porównuje ona dwa kolejne elementy zbioru i zamienia je miejscami, jeśli są w złej kolejności. Po zamianie do zmiennej p trafia indeks pierwszego z elementów pary. Podany warunek sprawdza uporządkowanie rosnące. Jeśli chcemy posortować zbiór malejąco, relację większości należy zastąpić relacją mniejszości.
W algorytmie występują trzy pętle.
Pętla nr 2 jest pętlą sortującą w górę.
Na początku algorytmu ustalamy dwie granice sortowania:
Granice te określają indeksy elementów zbioru, które będą przeglądały pętle
sortujące
Na początku pętli
Pierwszą pętlę sortującą wykonujemy kolejno dla indeksów od
pmin do pmax.
Po zakończeniu pętli sprawdzamy, czy p jest równe 0.
Jeśli tak, kończymy algorytm. W przeciwnym razie p
zawiera pozycję ostatniej zamiany elementów. Ponieważ pętla
Przed rozpoczęciem drugiej pętli zerujemy p. Jest to
dosyć ważne. Załóżmy, iż zbiór został już uporządkowany w poprzedniej pętli
Pętla nr 3 sortuje w kierunku odwrotnym od pmax
do
pmin. Po jej zakończeniu p
zawiera indeks ostatniej zamiany elementów. Podobnie jak poprzednio zbiór jest
uporządkowany od elementu nr 1 do p. Zatem dla kolejnych
obiegów przyjmujemy pmin o 1 większe od
p. Jeśli p jest równe 0, kończymy
algorytm. W przeciwnym razie kontynuujemy pętlę
C++// Dwukierunkowe Sortowanie Bąbelkowe //-------------------------------------------------------- // (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,pmin,pmax,p; cout << "Dwukierunkowe Sortowanie babelkowe\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 pmin = 0; pmax = N - 2; do { p = -1; for(i = pmin; i <= pmax; i++) if(d[i] > d[i + 1]) { swap(d[i], d[i + 1]); p = i; } if(p < 0) break; pmax = p - 1; p = -1; for(i = pmax; i >= pmin; i--) if(d[i] > d[i + 1]) { swap(d[i], d[i + 1]); p = i; } pmin = p + 1; } while(p >= 0); // 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// Dwukierunkowe Sortowanie Bąbelkowe //----------------------------------- // (C)2012 mgr Jerzy Wałaszek // I Liceum Ogólnokształcące // im. K. Brodzińskiego // w Tarnowie //-------------------------------------------------------- program Bidirectional_Bubble_Sort; const N = 20; // Liczebność zbioru. var d : array[1..N] of integer; // Program główny //--------------- var i,p,pmin,pmax,x: integer; begin writeln('Dwukierunkowe sortowanie babelkowe'); 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 pmin := 1; pmax := N - 1; repeat p := 0; for i := pmin to pmax do if d[i] > d[i + 1] then begin x := d[i]; d[i] := d[i+1]; d[i+1] := x; p := i; end; if p = 0 then break; pmax := p - 1; p := 0; for i := pmax downto pmin do if d[i] > d[i + 1] then begin x := d[i]; d[i] := d[i+1]; d[i+1] := x; p := i; end; pmin := p + 1; until p = 0; // 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' Dwukierunkowe Sortowanie Bąbelkowe '----------------------------------- ' (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 DIM i AS INTEGER, p AS INTEGER, pmin AS INTEGER, pmax AS INTEGER PRINT "Dwukierunkowe sortowanie babelkowe" 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 pmin = 1: pmax = N - 1 DO p = 0 FOR i = pmin TO pmax IF d(i) > d(i + 1) THEN SWAP d(i), d(i + 1) p = i END IF NEXT IF p = 0 THEN EXIT DO pmax = p - 1 p = 0 FOR i = pmax TO pmin STEP -1 IF d(i) > d(i + 1) THEN SWAP d(i), d(i + 1) p = i END IF NEXT pmin = p + 1 LOOP UNTIL p = 0 ' 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,pmin,pmax,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 pmin = 0; pmax = N - 2; do { p = -1; for(i = pmin; i <= pmax; i++) if(d[i] > d[i + 1]) { x = d[i]; d[i] = d[i+1]; d[i+1] = x; p = i; } if(p < 0) break; pmax = p - 1; p = -1; for(i = pmax; i >= pmin; i--) if(d[i] > d[i + 1]) { x = d[i]; d[i] = d[i+1]; d[i+1] = x; p = i; } pmin = p + 1; } while(p >= 0); // 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: |
Dwukierunkowe Sortowanie
babelkowe ---------------------------------- (C)2005 Jerzy Walaszek Przed sortowaniem: 22 67 9 15 4 3 21 40 66 83 89 38 31 42 92 55 3 87 48 50 Po sortowaniu: 3 3 4 9 15 21 22 31 38 40 42 48 50 55 66 67 83 87 89 92 |
W celach badawczych testujemy czas wykonania algorytmu dwukierunkowego sortowania bąbelkowego 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 = 'Dwukierunkowe sortowanie bąbelkowe'; 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,p,pmin,pmax : integer; x : real; begin QueryPerformanceCounter(addr(qpc1)); pmin := 1; pmax := n - 1; repeat p := 0; for i := pmin to pmax do if d[i] > d[i + 1] then begin x := d[i]; d[i] := d[i+1]; d[i+1] := x; p := i; end; if p = 0 then break; pmax := p - 1; p := 0; for i := pmax downto pmin do if d[i] > d[i + 1] then begin x := d[i]; d[i] := d[i+1]; d[i+1] := x; p := i; end; pmin := p + 1; until p = 0; 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: Dwukierunkowe sortowanie bąbelkowe 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 dwukierunkowego sortowania bąbelkowego wyciągamy
następujące wnioski:
Cechy Algorytmu Dwukierunkowego Sortowania Bąbelkowego |
|
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 |
Dwukierunkowe |
|||||
Wzrost prędkości sortowania | |||||
Algorytmy | tpo | tod | tpp | tpk | tnp |
Sortowanie bąbelkowe 4 Dwukierunkowe sortowanie bąbelkowe |
|||||
brak | lepiej | brak | gorzej | lepiej |
Zobacz również na: Wersję 1 | Wersję 2 | Wersję 3 | Wersję 4
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.