Dwukierunkowe sortowanie bąbelkowe
           Bidirectional Bubble Sort
           Cocktail Sort


Podrozdziały     Tematy pokrewne

 

Algorytm

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.

 

Specyfikacja problemu

Dane wejściowe

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.

Dane wyjściowe

d[ ] - posortowany zbiór n-elementowy. Elementy zbioru mają indeksy od 1 do n.

Zmienne pomocnicze

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

 

Lista kroków

Operacja sortująca

K01: Jeśli d[i] ≤ d[i + 1], to zakończ operację sortującą
K02: d[i] ↔ d[i + 1]
K03: pi
K04: Zakończ operację sortującą

Algorytm główny

K01: pmin ← 1;   pmaxn - 1
K02: p ← 0
K03:     Dla i = pmin, pmin + 1, ..., pmax: wykonuj operację sortującą
K04:     Jeśli p = 0, to zakończ
K05:     pmaxp - 1;   p ← 0
K06:     Dla i = pmax, pmax - 1, ..., pmin: wykonuj operację sortującą
K07:     pminp + 1
K08:     Jeśli p > 0, to idź do K02
K09: Zakończ

 

Schemat blokowy

flow

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 1 jest pętlą warunkową i obejmuje dwie pętle wewnętrzne nr 2 i nr 3. Pętla ta wykonywana jest dotąd, aż w sortowanym zbiorze nie wystąpi w trakcie sortowania ani jedna zamiana miejsc elementów.

Pętla nr 2 jest pętlą sortującą w górę. Pętla nr 3 sortuje w dół.

Na początku algorytmu ustalamy dwie granice sortowania:

 

- dolną w pmin
- górną w pmax.

 

Granice te określają indeksy elementów zbioru, które będą przeglądały pętle sortujące nr 2 i nr 3. Początkowo granice są tak ustawione, iż obejmują cały sortowany zbiór.

Na początku pętli nr 1 zerujemy zmienną p. Zmienna ta będzie zapamiętywać pozycję ostatniej zamiany elementów. Jeśli po przejściu pętli sortującej nr 2 lub nr 3 zmienna p wciąż zawiera wartość 0, to nie wystąpiła żadna zamiana elementów. Zbiór jest wtedy uporządkowany i kończymy algorytm.

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 nr 2 ustala pozycję najstarszego elementu, to elementy o indeksach od p do n są już właściwie uporządkowane. Dlatego dla kolejnego obiegu pętli przyjmujemy pmax o 1 mniejsze niż p.

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 nr 2, lecz wystąpiła tam zamiana elementów. Jeśli nie wyzerujemy p, to następna pętla sortująca nie zmieni zawartości tej zmiennej i p zachowa wartość większą od 0. Zatem pętla główna nr 1 nie zakończy się i algorytm wykona niepotrzebnie jeszcze jeden pusty obieg. Niby nic, a jednak...

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ę nr 1.

Programy

Efekt uruchomienia programu
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

 

DevPascal
// 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.
Code::Blocks
// 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;
}
Free 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>

 

Tutaj możesz przetestować działanie prezentowanego skryptu:

Dwukierunkowe Sortowanie Bąbelkowe

(C)2012 mgr Jerzy Wałaszek - I LO w Tarnowie


...

 

Einstein
DLA
GENIUSZA

Badanie algorytmów sortowania

W celach badawczych testujemy czas wykonania algorytmu dwukierunkowego sortowania bąbelkowego 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 = '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
--------------------------------------------------
(C)2011/2012 I Liceum Ogolnoksztalcace w Tarnowie

------n---------tpo---------tod---------tpp---------tpk---------tnp
1000 0.000008 0.025453 0.000042 0.000035 0.016423
2000 0.000015 0.101098 0.000085 0.000076 0.062626
4000 0.000027 0.400720 0.000157 0.000141 0.241540
8000 0.000051 1.608819 0.000226 0.000232 0.968169
16000 0.000114 6.432362 0.000663 0.000573 3.876952
32000 0.000282 25.828298 0.001269 0.001122 15.551078
-------------------------------------------------------------------
Koniec

Objaśnienia oznaczeń (wszystkie czasy podano w sekundach):

n -  ilość elementów w sortowanym zbiorze
tpo -  czas sortowania zbioru posortowanego
tod -  czas sortowania zbioru posortowanego malejąco
tpp -  czas sortowania zbioru posortowanego z losowym elementem na początku
tpk -  czas sortowania zbioru posortowanego z losowym elementem na końcu
tnp -  czas sortowania zbioru z losowym rozkładem elementów

(Arkusz kalkulacyjny Excel do wyznaczania klasy czasowej złożoności obliczeniowej)

(Arkusz kalkulacyjny Excel do wyznaczania wzrostu prędkości sortowania)

Podsumowanie

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 O(n)
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
Dwukierunkowe
sortowanie bąbelkowe
O(n) O(n2) O(n) O(n) O(n2)
tpo << tod
tpp  9 tpk
8
tnp  3 tod
5
  1. W przypadku zbioru posortowanego odwrotnie oraz zbioru nieuporządkowanego algorytm wykonuje się w czasie proporcjonalnym do kwadratu liczby elementów, zatem jego typowa czasowa złożoność obliczeniowa jest klasy O(n2).
  2. Zbiór nieuporządkowany sortowany jest szybciej od zbioru uporządkowanego odwrotnie. Wnioskujemy zatem, iż zbiór uporządkowany odwrotnie jest najtrudniejszym zadaniem dla tego algorytmu.
  3. Przy sortowaniu zbiorów w znacznym stopniu posortowanych klasa czasowej złożoności obliczeniowej redukuje się do O(n), jest zatem bardzo korzystna.
  4. W porównaniu do zoptymalizowanego algorytmu bąbelkowego w wersji 4 algorytm dwukierunkowego sortowania bąbelkowego nie wykazuje specjalnie nowych własności. Obserwujemy jedynie wyrównanie czasów sortowania zbioru uporządkowanego z jednym elementem losowym na początku i na końcu.
Wzrost prędkości sortowania
Algorytmy tpo tod tpp tpk tnp
Sortowanie bąbelkowe 4

Dwukierunkowe sortowanie bąbelkowe

  1
  7
6
  1
  7
10
  6
5
brak lepiej brak gorzej lepiej
  1. Jeśli porównamy prędkości obu algorytmów, to obecna wersja radzi sobie nieco lepiej w przypadku zbiorów uporządkowanych odwrotnie oraz zbiorów nieuporządkowanych. W pozostałych sytuacjach jest bez zmian, lub nawet gorzej.

Zadania dla ambitnych

  1. Uzasadnij wyrównanie czasów tpp i tpk w algorytmie dwukierunkowego sortowania bąbelkowego.

Zobacz również na: Wersję 1 | Wersję 2 | Wersję 3 | Wersję 4

 



List do administratora Serwisu Edukacyjnego Nauczycieli I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

 

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   
im. Kazimierza Brodzińskiego
w Tarnowie

©2017 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.