Do strony głównej I LO w Tarnowie   Wyjście Spis treści

Prezentowane materiały są przeznaczone dla uczniów szkół ponadgimnazjalnych.
Autor artykułu: mgr Jerzy Wałaszek,  Wersja 4.1

 ©2011 mgr Jerzy Wałaszek
I LO w Tarnowie

Sortowanie bąbelkowe - wersja nr 3
           Bubble Sort

Podrozdziały     Tematy pokrewne

Algorytm

Specyfikacja problemu

Lista kroków

Schemat blokowy

Programy

Program w języku Pascal

Program w języku C++

Program w języku Basic

Program w języku JavaScript

Badanie algorytmów sortujących

Podsumowanie

Zadania dla ambitnych

Wersja 1

Wersja 2

Wersja 4

Dwukierunkowe sortowanie bąbelkowe

 

Algorytm

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

  1. Wersja pierwsza jest najmniej optymalną wersją algorytmu bąbelkowego. Wykonywane są wszystkie możliwe operacje sortujące i puste.
  2. 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(n2).

 

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.


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

pic

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.



Programy

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

 

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

 

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

Sortowanie Bąbelkowe - wersja nr 3

(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 3 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 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
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 3 wyciągamy następujące wnioski:

Cechy Algorytmu Sortowania Bąbelkowego
wersja nr 3
klasa złożoności obliczeniowej optymistyczna O(n) -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 3		 O(n) O(n2) O(n) O(n2) O(n2)
tpo << tod tpp << tpk
tnp ≈   3 tod
5
  1. 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).
  2. 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(n2).
Wzrost prędkości sortowania
Algorytmy tpo tod tpp tpk tnp
Sortowanie bąbelkowe 2

Sortowanie bąbelkowe 3
≈   2 n
5
≈   1
≈   0,07n
≈   3
2
≈   1
dobrze  brak dobrze dobrze brak
  1. 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.

Zadania dla ambitnych

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

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

 

 

   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie
©2018 mgr Jerzy Wałaszek
Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe