Algorytmy Sortujące - Sortowanie Bąbelkowe Dwukierunkowe

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.

do podrozdziału do strony

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
p_min	- dolna granica pozycji sortowanych elementów, p_min ∈ N
p_max	- górna granica pozycji sortowanych elementów, p_max ∈ 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:	p ← i
K04:	Zakończ operację sortującą

Algorytm główny

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

Schemat blokowy

obrazek

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 p_min
- górną w p_max.

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 p_min do p_max. 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 p_max 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 p_max do p_min. 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 p_min o 1 większe od p. Jeśli p jest równe 0, kończymy algorytm. W przeciwnym razie kontynuujemy pętlę nr 1.

do podrozdziału do strony

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

do podrozdziału do strony

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
--------------------------------------------------
(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
t_po	-	czas sortowania zbioru posortowanego
t_od	-	czas sortowania zbioru posortowanego malejąco
t_pp	-	czas sortowania zbioru posortowanego z losowym elementem na początku
t_pk	-	czas sortowania zbioru posortowanego z losowym elementem na końcu
t_np	-	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)

do podrozdziału do strony

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:

optymistyczna - dla zbiorów uporządkowanych (z niewielką liczbą elementów nie na swoich miejscach) - na podstawie czasów t_po, t_pp, t_pk
typowa - dla zbiorów o losowym rozkładzie elementów - na podstawie czasu t_np
pesymistyczna - dla zbiorów posortowanych odwrotnie - na podstawie czasu t_od.

Własności algorytmu
Algorytm	t_po	t_od	t_pp	t_pk	t_np
Dwukierunkowe sortowanie bąbelkowe
Dwukierunkowe sortowanie bąbelkowe

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(n²).
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.
Przy sortowaniu zbiorów w znacznym stopniu posortowanych klasa czasowej złożoności obliczeniowej redukuje się do O(n), jest zatem bardzo korzystna.
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	t_po	t_od	t_pp	t_pk	t_np
Sortowanie bąbelkowe 4 Dwukierunkowe sortowanie bąbelkowe
Sortowanie bąbelkowe 4 Dwukierunkowe sortowanie bąbelkowe	brak	lepiej	brak	gorzej	lepiej

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.

do podrozdziału do strony

Uzasadnij wyrównanie czasów t_pp i t_pk w algorytmie dwukierunkowego sortowania bąbelkowego.

do podrozdziału do strony

Dwukierunkowe sortowanie bąbelkowe
Bidirectional Bubble Sort
Cocktail Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Operacja sortująca

Algorytm główny

Schemat blokowy

Przykładowe programy

Dwukierunkowe Sortowanie Bąbelkowe

Badania algorytmów sortowania

Podsumowanie

Zadania dla ambitnych

Dwukierunkowe sortowanie bąbelkowe Bidirectional Bubble Sort Cocktail Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Operacja sortująca

Algorytm główny

Schemat blokowy

Przykładowe programy

Dwukierunkowe Sortowanie Bąbelkowe

Badania algorytmów sortowania

Podsumowanie

Zadania dla ambitnych

Dwukierunkowe sortowanie bąbelkowe
Bidirectional Bubble Sort
Cocktail Sort