Algorytmy Sortujące - Sortowanie Bąbelkowe

Podany w poprzednim rozdziale algorytm sortowania bąbelkowego można zoptymalizować pod względem czasu wykonania. Jeśli przyjrzymy się dokładnie obiegom wykonywanym w tym algorytmie, to zauważymy bardzo istotną rzecz:

Po wykonaniu pełnego obiegu w algorytmie sortowania bąbelkowego najstarszy element wyznaczony przez przyjęty porządek zostaje umieszczony na swoim właściwym miejscu - na końcu zbioru.

Wniosek ten jest oczywisty. W każdej kolejnej parze porównywanych elementów element starszy przechodzi na drugą pozycję. W kolejnej parze jest on na pierwszej pozycji, a skoro jest najstarszym, to po porównaniu znów przejdzie na pozycję drugą itd. - jest jakby ciągnięty na koniec zbioru (jak bąbelek powietrza wypływający na powierzchnię wody).

Przykład:

Wykonamy jeden obieg sortujący dla zbioru pięcioelementowego

{ 9 3 1 7 0 }. Elementem najstarszym jest pierwszy element - liczba 9.

Obieg	Zbiór	Opis operacji
1	9 3 1 7 0	Para wymaga przestawienia elementów. Element najstarszy przejdzie na drugą pozycję w parze.
	3 9 1 7 0	Konieczne przestawienie elementów. Element najstarszy znów trafi na pozycję drugą w parze.
	3 1 9 7 0	Konieczne przestawienie elementów.
	3 1 7 9 0	Ostatnia para również wymaga przestawienia elementów.
	3 1 7 0 9	Koniec obiegu. Najstarszy element znalazł się na końcu zbioru.

Co z tego wynika dla nas? Otóż po każdym obiegu na końcu zbioru tworzy się podzbiór uporządkowanych najstarszych elementów. Zatem w kolejnych obiegach możemy pomijać sprawdzanie ostatnich elementów - liczebność zbioru do posortowania z każdym obiegiem maleje o 1.

Przykład:

Dokończmy sortowania podanego powyżej zbioru uwzględniając podane przez nas fakty. Po pierwszym obiegu na końcu zbioru mamy umieszczony element najstarszy. W drugim obiegu będziemy zatem sortować zbiór 4 elementowy, w trzecim obiegu 3 elementowy i w obiegu ostatnim, czwartym - zbiór 2 elementowy.

Obieg	Zbiór	Opis operacji
2	3 1 7 0 9	Para wymaga przestawienia elementów.
	1 3 7 0 9	Dobra kolejność
	1 3 7 0 9	Konieczne przestawienie elementów.
	1 3 0 7 9	Koniec obiegu. Na końcu zbioru mamy 2 elementy uporządkowane.
3	1 3 0 7 9	Dobra kolejność
	1 3 0 7 9	Konieczne przestawienie elementów.
	1 0 3 7 9	Koniec obiegu. Na końcu zbioru mamy 3 elementy uporządkowane.
4	1 0 3 7 9	Konieczne przestawienie elementów.
4	0 1 3 7 9	Koniec ostatniego obiegu - zbiór jest posortowany.

W porównaniu do tabelki z poprzedniego rozdziału nawet wzrokowo możemy zauważyć istotne zmniejszenie ilości niezbędnych operacji.

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

Lista kroków

K01:	Dla j = n - 1, n - 2, ..., 1: Wykonuj krok K02
K02:	Dla i = 1, 2, ..., j: jeśli d[i] > d[i + 1], to d[i] ↔ d[i + 1]
K03:	Zakończ

Schemat blokowy

obrazek

Zmiany w stosunku do poprzedniej wersji zaznaczyliśmy na schemacie blokowym innym kolorem elementów. Są one następujące:

pętla zewnętrzna nr 1 zlicza obiegi wstecz, tzn. pierwszy obieg ma numer n-1. Dzięki takiemu podejściu w zmiennej j mamy zawsze numer ostatniego elementu, do którego ma dojść pętla wewnętrzna nr 2. Ta zmiana wymaga również odwrotnej iteracji zmiennej j.
pętla wewnętrzna sprawdza w warunku kontynuacji, czy wykonała j obiegów, a nie jak poprzednio n-1 obiegów. Dzięki temu po każdym obiegu pętli nr 1 (zewnętrznej) pętla nr 2 będzie wykonywać o jeden obieg mniej.

Pozostała część algorytmu nie jest zmieniona - w pętli wewnętrznej nr 2 sprawdzamy, czy element d[i] jest w złej kolejności z elementem d[i+1]. Sprawdzany warunek spowoduje posortowanie zbioru rosnąco. Przy sortowaniu malejącym zmieniamy relację większości na relację mniejszości. Jeśli warunek jest spełniony, zamieniamy miejscami element d[i] z elementem d[i+1], po czym kontynuujemy pętlę nr 2 zwiększając o 1 indeks i. Po każdym zakończeniu pętli nr 2 indeks j jest zmniejszany o 1.

Ilość obiegów pętli wewnętrznej wynosi:

Otrzymane wyrażenie ma wciąż kwadratową klasę złożoności obliczeniowej, jednakże T₂(n) < T₁(n) dla n > 1. Osiągnęliśmy zatem większą efektywność działania dzięki wprowadzonym zmianom.

do podrozdziału do strony

C++

// Sortowanie Bąbelkowe - Wersja nr 2
//--------------------------------------------------------
// (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;
  
  cout << " Sortowanie babelkowe\n"
          "     WERSJA NR 2\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--)
    for(i = 0; i < j; i++)
      if(d[i] > d[i + 1]) swap(d[i], d[i + 1]);

// 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 2
//--------------------------------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie
//--------------------------------------------------------

program Bubble_Sort_2;

const N = 20; // Liczebność zbioru.

var
  d : array[1..N] of integer;

// Program główny
//---------------

var
  i,j,x : integer;
begin
  writeln(' Sortowanie babelkowe ');
  writeln('     WERSJA  NR 2     ');
  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
    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;
      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 2
'--------------------------------------------------------
' (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

  PRINT " Sortowanie babelkowe "
  PRINT "     WERSJA  NR 2     "
  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
    FOR i = 1 TO j
      IF d(i) > d(i+1) THEN SWAP d(i), d(i+1)
    NEXT
  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 2</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 2
//--------------------------------------------------------
// (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,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--)
    for(i = 0; i < j; i++)
      if(d[i] > d[i + 1])
      {
        x = d[i]; d[i] = d[i + 1]; d[i + 1] = x;
      };

  // 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 2
----------------------
(C)2005 Jerzy Walaszek

Przed sortowaniem:

44 29 43 80 95 88 40 45 28 13   8 90 49 28 76 64 22 70   4   6

Po sortowaniu:

   4   6   8 13 22 28 28 29 40 43 44 45 49 64 70 76 80 88 90 95

do podrozdziału do strony

W celach badawczych testujemy czas wykonania algorytmu sortowania bąbelkowego 2 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 2';
  K1    = '--------------------------------------------------';
  K2    = '(C)2011/2012 I Liceum Ogolnoksztalcace  w Tarnowie';
  K3    = '------n---------tpo---------tod---------tpp---------tpk---------tnp';
  K4    = '-------------------------------------------------------------------';
  MAX_LN = 5; // 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 : integer;
  x   : real;
begin
  QueryPerformanceCounter(addr(qpc1));
  for j := n - 1 downto 1 do
    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;
      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 2
--------------------------------------------------
(C)2011/2012 I Liceum Ogolnoksztalcace  w Tarnowie

------n---------tpo---------tod---------tpp---------tpk---------tnp
   1000    0.003118    0.030915    0.003249    0.003674    0.019875
   2000    0.012156    0.124258    0.013537    0.014906    0.074068
   4000    0.052770    0.499130    0.049157    0.048772    0.296212
   8000    0.194066    1.995982    0.196131    0.196660    1.191403
  16000    0.775087    7.993864    0.800502    0.786996    4.756371
-------------------------------------------------------------------
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 2 wyciągamy następujące wnioski:

Cechy Algorytmu Sortowania Bąbelkowego wersja nr 2
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 2
Sortowanie bąbelkowe wersja nr 2

Wszystkie czasy sortowania są proporcjonalne do kwadratu liczby elementów w sortowanych zbiorach, zatem klasa czasowej złożoności obliczeniowej jest równa O(n²).
Czasy sortowania t_po, t_pp oraz t_pk są praktycznie takie same.

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

Analizując wzrost prędkości algorytmu sortowania bąbelkowego w wersji 2 w stosunku do wersji 1 zauważamy, iż wprowadzona zmiana faktycznie zwiększyła ogólną prędkość działania. Jednakże korzyść w typowym przypadku zbioru nieuporządkowanego jest stosunkowo niewielka. Największy wzrost prędkości notujemy przy sortowaniu zbiorów częściowo uporządkowanych.

do podrozdziału do strony

Jakiego typu operacje są wykonywane w algorytmie sortowania bąbelkowego?
Na jakich operacjach zyskaliśmy w tej wersji algorytmu?
Które operacje dominują przy wyznaczaniu czasów t_po, t_pp oraz t_pk?
Uzasadnij wyniki otrzymane przy badaniu wzrostu prędkości algorytmu sortowania bąbelkowego w wersji 2 w stosunku do wersji 1.
Dokonaj analogicznego porównania wzrostu prędkości tego algorytmu w stosunku do algorytmu sortowania głupiego.

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 2
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 2

Badania algorytmów sortowania

Podsumowanie

Zadania dla ambitnych

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

Badania algorytmów sortowania

Podsumowanie

Zadania dla ambitnych

Sortowanie bąbelkowe - wersja nr 2
Bubble Sort