Algorytmy Sortujące - Sortowanie Bąbelkowe

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ń:

Wersja pierwsza jest najmniej optymalną wersją algorytmu bąbelkowego. Wykonywane są wszystkie możliwe operacje sortujące i puste.
Wersja druga redukuje ilość operacji pustych poprzez ograniczanie liczby obiegów pętli wewnętrznej (sortującej).

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 n - 1 operacji pustych, zatem w przypadku najbardziej optymistycznym czasowa złożoność obliczeniowa redukuje się do klasy O(n) - liniowej. W przypadku najbardziej niekorzystnym algorytm wykona wszystkie operacje puste i sortujące, zatem będzie posiadał klasę czasowej złożoności obliczeniowej O(n²).

Przykład:

Posortujmy zbiór { 3 1 0 7 9 } zgodnie z wprowadzoną modyfikacją.

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.

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, j	- zmienne sterujące pętli, i, j ∈ N
p	- znacznik zamiany miejsc elementów w zbiorze. p ∈ N

Lista kroków

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

Schemat blokowy

obrazek

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 32-bitowe. Standardowy typ boolean (w C++ bool) jest daną 8-bitową, która wydłuża wykonanie programu, ponieważ dostęp do takich danych zajmuje procesorowi Pentium o wiele więcej czasu niż dostęp do danych 32-bitowych.

do podrozdziału do strony

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

do podrozdziału do strony

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
--------------------------------------------------
(C)2011/2012 I Liceum Ogolnoksztalcace  w Tarnowie

------n---------tpo---------tod---------tpp---------tpk---------tnp
   1000    0.000008    0.030413    0.000042    0.002527    0.020769
   2000    0.000014    0.122591    0.000084    0.010772    0.072822
   4000    0.000025    0.487696    0.000164    0.032994    0.292399
   8000    0.000050    1.954120    0.000253    0.095668    1.181462
  16000    0.000119    7.963850    0.000707    0.539036    4.686158
  32000    0.000283   31.464163    0.001363    1.871901   18.937897
-------------------------------------------------------------------
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 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:

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
Sortowanie bąbelkowe wersja nr 3
Sortowanie bąbelkowe wersja nr 3

Wprowadzona zmiana wpłynęła na zmianę klasy czasowej złożoności obliczeniowej przy sortowaniu zbioru uporządkowanego oraz przy sortowaniu zbioru uporządkowanego z losowym elementem na początku. W obu przypadkach notujemy proporcjonalność czasu sortowania do liczby elementów w zbiorze, zatem klasa czasowej złożoności obliczeniowej wynosi O(n).
Nie zmieniła się natomiast klasa czasowej złożoności obliczeniowej przy sortowaniu zbioru uporządkowanego odwrotnie, przy sortowaniu zbioru uporządkowanego z losowym elementem na końcu oraz przy sortowaniu zbioru nieuporządkowanego. Dlatego w przypadku ogólnym klasa czasowej złożoności obliczeniowej wynosi O(n²).

Wzrost prędkości sortowania
Algorytmy	t_po	t_od	t_pp	t_pk	t_np
Sortowanie bąbelkowe 2 Sortowanie bąbelkowe 3
Sortowanie bąbelkowe 2 Sortowanie bąbelkowe 3	dobrze	brak	dobrze	dobrze	brak

Analizując wzrost prędkości algorytmu sortowania bąbelkowego w wersji 3 w stosunku do wersji 2 zauważamy, iż wprowadzona zmiana nie zwiększyła prędkości działania algorytmu dla przypadku zbioru posortowanego odwrotnie oraz dla zbioru nieuporządkowanego. Największy zysk (zmniejszenie klasy czasowej złożoności obliczeniowej) występuje przy sortowaniu zbiorów częściowo uporządkowanych.

do podrozdziału do strony

Uzasadnij zmianę klasy czasowej złożoności obliczeniowej z O(n²) dla operacji sortowania zbioru uporządkowanego w wersjach nr 1 i 2 algorytmu sortowania bąbelkowego na klasę O(n) w wersji nr 3.
Dlaczego nie uzyskaliśmy istotnego wzrostu prędkości pracy algorytmu dla przypadku zbioru posortowanego odwrotnie oraz zbioru nieuporządkowanego.
Zbadaj wzrost prędkości algorytmu sortowania bąbelkowego w wersji nr 3 w stosunku do wersji nr 2. Wyciągnij odpowiednie wnioski.

do podrozdziału do strony

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: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Sortowanie bąbelkowe - wersja nr 3
Bubble Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Sortowanie Bąbelkowe - wersja nr 3

Badania algorytmów sortowania

Podsumowanie

Zadania dla ambitnych

Sortowanie bąbelkowe - wersja nr 3 Bubble Sort

Algorytm

Opis algorytmu

Specyfikacja problemu

Dane wejściowe

Dane wyjściowe

Zmienne pomocnicze

Lista kroków

Schemat blokowy

Przykładowe programy

Sortowanie Bąbelkowe - wersja nr 3

Badania algorytmów sortowania

Podsumowanie

Zadania dla ambitnych

Sortowanie bąbelkowe - wersja nr 3
Bubble Sort