Sortowanie bąbelkowe - wersja nr 2
           Bubble Sort


Podrozdziały     Tematy pokrewne

 

Algorytm

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

 

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

flow

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:

 

        

T2(n) = (n-1) + (n-2) + ... + 2 + 1 =

n(n - 1)  = 1 (n2 - n)         
2 2

 

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

 

Programy

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

 

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


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

Sortowanie Bąbelkowe - wersja nr 2

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


...

 

Einstein
DLA
GENIUSZA

Badania algorytmów sortowania

W celach badawczych testujemy czas wykonania algorytmu sortowania bąbelkowego 2 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 = '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
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 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 O(n2)
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
Sortowanie bąbelkowe
wersja nr 2
O(n2) O(n2) O(n2) O(n2) O(n2)
tpo   1 tod
10
tpo=tpp=tpk
tnp ≈  3 tod
5
  1. 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(n2).
  2. Czasy sortowania tpo, tpp oraz tpk są praktycznie takie same.
Wzrost prędkości sortowania
Algorytmy tpo tod tpp tpk tnp
Sortowanie bąbelkowe 1

Sortowanie bąbelkowe 2

≈  13
6
≈  11
10
≈  2
≈  2
≈  7
6
dobrze niewiele dobrze dobrze niewiele
  1. 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.

Zadania dla ambitnych

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

Zobacz również na: Wersję 1 | Wersję 3 | Wersję 4 | Dwukierunkowe sortowanie bąbelkowe

 



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.