Algorytmy Sortujące - Sortowanie Bąbelkowe

Algorytm sortowania bąbelkowego jest jednym z najstarszych algorytmów sortujących. Można go potraktować jako ulepszenie opisanego w poprzednim rozdziale algorytmu sortowania głupiego. Zasada działania opiera się na cyklicznym porównywaniu par sąsiadujących elementów i zamianie ich kolejności w przypadku niespełnienia kryterium porządkowego zbioru. Operację tę wykonujemy dotąd, aż cały zbiór zostanie posortowany.

Algorytm sortowania bąbelkowego przy porządkowaniu zbioru nieposortowanego ma klasę czasowej złożoności obliczeniowej równą O(n²). Sortowanie odbywa się w miejscu.

Przykład:

Jako przykład działania algorytmu sortowania bąbelkowego posortujemy przy jego pomocy 5-cio elementowy zbiór liczb { 5 4 3 2 1 }, który wstępnie jest posortowany w kierunku odwrotnym, co możemy uznać za przypadek najbardziej niekorzystny, ponieważ wymaga przestawienia wszystkich elementów.

Obieg	Zbiór	Opis operacji
1	5 4 3 2 1	Rozpoczynamy od pierwszej pary, która wymaga wymiany elementów
	4 5 3 2 1	Druga para też wymaga zamiany elementów
	4 3 5 2 1	Wymagana wymiana elementów
	4 3 2 5 1	Ostatnia para również wymaga wymiany elementów
	4 3 2 1 5	Stan po pierwszym obiegu. Zwróć uwagę, iż najstarszy element 5 znalazł się na końcu zbioru, a najmłodszy 1 przesunął się o jedną pozycję w lewo.
2	4 3 2 1 5	Para wymaga wymiany
	3 4 2 1 5	Para wymaga wymiany
	3 2 4 1 5	Para wymaga wymiany
	3 2 1 4 5	Elementy są w dobrej kolejności, zamiana nie jest konieczna.
	3 2 1 4 5	Stan po drugim obiegu. Zwróć uwagę, iż najmniejszy element 1 znów przesunął się o jedną pozycję w lewo. Z obserwacji tych można wywnioskować, iż po każdym obiegu najmniejszy element wędruje o jedną pozycję ku początkowi zbioru. Najstarszy element zajmuje natomiast swe miejsce końcowe.
3	3 2 1 4 5	Para wymaga wymiany
	2 3 1 4 5	Para wymaga wymiany
	2 1 3 4 5	Dobra kolejność
	2 1 3 4 5	Dobra kolejność
	2 1 3 4 5	Stan po trzecim obiegu. Wnioski te same.
4	2 1 3 4 5	Para wymaga wymiany
	1 2 3 4 5	Dobra kolejność
	1 2 3 4 5	Dobra kolejność
	1 2 3 4 5	Dobra kolejność
	1 2 3 4 5	Zbiór jest posortowany. Koniec

Posortowanie naszego zbioru wymaga 4 obiegów. Jest to oczywiste: w przypadku najbardziej niekorzystnym najmniejszy element znajduje się na samym końcu zbioru wejściowego. Każdy obieg przesuwa go o jedną pozycję w kierunku początku zbioru. Takich przesunięć należy wykonać n - 1 (n - ilość elementów w zbiorze).

Algorytm sortowania bąbelkowego, w przeciwieństwie do algorytmu sortowania głupiego, nie przerywa porównywania par elementów po napotkaniu pary nie spełniającej założonego porządku. Po zamianie kolejności elementów sprawdzana jest kolejna para elementów sortowanego zbioru. Dzięki temu podejściu rośnie efektywność algorytmu oraz zmienia się klasa czasowej złożoności obliczeniowej z O(n³) na O(n²).

Uwaga:

Algorytm sortowania bąbelkowego jest uważany za bardzo zły algorytm sortujący. Można go stosować tylko dla niewielkiej liczby elementów w sortowanym zbiorze (do około 5000). Przy większych zbiorach czas sortowania może być zbyt długi.

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 = 1,2,...,n - 1: Wykonuj krok K02
K02:	Dla i = 1,2,...,n - 1: Jeśli d[i] > d[i + 1], to d[i] ↔ d[i + 1]
K03:	Zakończ

Schemat blokowy

Sortowanie wykonywane jest w dwóch zagnieżdżonych pętlach. Pętla zewnętrzna nr 1 kontrolowana jest przez zmienną j. Wykonuje się ona n - 1 razy. Wewnątrz pętli nr 1 umieszczona jest pętla nr 2 sterowana przez zmienną i. Wykonuje się również n - 1 razy. W efekcie algorytm wykonuje w sumie:

obiegów pętli wewnętrznej, po których zakończeniu zbiór zostanie posortowany.

Sortowanie odbywa się wewnątrz pętli nr 2. Kolejno porównywany jest i-ty element z elementem następnym. Jeśli elementy te są w złej kolejności, to zostają zamienione miejscami. W tym miejscu jest najważniejsza różnica pomiędzy algorytmem sortowania bąbelkowego a algorytmem sortowania głupiego. Ten drugi w momencie napotkania elementów o złej kolejności zamienia je miejscami i rozpoczyna cały proces sortowania od początku. Algorytm sortowania bąbelkowego wymienia miejscami źle ułożone elementy sortowanego zbioru i przechodzi do następnej pary zwiększając indeks i o 1. Dzięki takiemu podejściu rośnie efektywność, co odzwierciedla klasa czasowej złożoności obliczeniowej:

Sortowanie głupie - O(n³); Sortowanie bąbelkowe - O(n²).

do podrozdziału do strony

C++

// Sortowanie Bąbelkowe - Wersja nr 1
//-----------------------------------
// (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 1\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 = 0; j < N - 1; j++)
    for(i = 0; i < N - 1; 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 1
//-----------------------------------
// (C)2012 mgr Jerzy Wałaszek
// I Liceum Ogólnokształcące
// im. K. Brodzińskiego
// w Tarnowie

program Bubble_Sort_1;

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 1     ');
  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;
  writeln;

  // Sortujemy
  for j := 1 to N - 1 do
    for i := 1 to N - 1 do
      if d[i] > d[i+1] then // Porządek rosnący
      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;
  writeln('Nacisnij Enter...');
  readln;
end.

Basic

' Sortowanie Bąbelkowe - Wersja nr 1
'-----------------------------------
' (C)2012 mgr Jerzy Wałaszek
' I Liceum Ogólnokształcące
' im. K. Brodzińskiego
' w Tarnowie

CONST N = 20 ' Liczebność zbioru.

DIM AS INTEGER d(1 TO N), i, j

PRINT " Sortowanie babelkowe "
PRINT "     WERSJA  NR 1     "
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
PRINT

' Sortujemy

FOR j = 1 TO N - 1
  FOR i = 1 TO N - 1
    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
PRINT "Nacisnij Enter..."
SLEEP
END

Python (dodatek)

# Sortowanie Bąbelkowe - Wersja nr 1
#-----------------------------------
# (C)2026 mgr Jerzy Wałaszek
# I Liceum Ogólnokształcące
# im. K. Brodzińskiego
# w Tarnowie

import random

n = 20 # Liczebność zbioru.

# sortowany zbiór
d = [random.randrange(100) for i in range(n)]

print(" Sortowanie bąbelkowe ")
print("     WERSJA  NR 1     ")
print("----------------------")
print("(C)2026 Jerzy Walaszek")
print()

# Wyświetlamy zbiór
print("Przed sortowaniem:")
print()
for i in range(n):
    print("%4d" % (d[i]),end="")
print()
print()

# Sortujemy
for j in range(n-1):
    for i in range(n-1):
        if d[i] > d[i+1]:
            d[i],d[i+1] = d[i+1],d[i]

# Wyświetlamy wynik sortowania
print("Po sortowaniu:")
print()
for i in range(n):
    print("%4d" % (d[i]),end="")
print()
print()
input("Naciśnij Enter...")

Wynik:

 Sortowanie bąbelkowe 
     WERSJA  NR 1     
----------------------
(C)2026 Jerzy Walaszek

Przed sortowaniem:

  63   2   0  70  95   2  50  78  86  17   5  56  33  18  11  21   3  89  76  80

Po sortowaniu:

   0   2   2   3   5  11  17  18  21  33  50  56  63  70  76  78  80  86  89  95

Naciśnij Enter...

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 1</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 1
//--------------------------------------------------------
// (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 = 0; j < N - 1; j++)
    for(i = 0; i < N - 1; 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>

do podrozdziału do strony

W celach badawczych testujemy czas wykonania algorytmu sortowania bąbelkowego 1 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 1';
  K1    = '--------------------------------------------------';
  K2    = '(C)2011/2012 mgr Jerzy Walaszek';
  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 := 1 to n - 1 do
    for i := 1 to n - 1 do
      if d[i] > d[i+1] then // Porządek rosnący
      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)

(Arkusz kalkulacyjny Excel do wyznaczania klasy czasowej złożoności obliczeniowej)
(Arkusz kalkulacyjny Excel do wyznaczania wzrostu prędkości sortowania)

Zawartość pliku wygenerowanego przez program

Nazwa: Sortowanie bąbelkowe - Bubble Sort 1
--------------------------------------------------
(C)2011/2012 mgr Jerzy Walaszek

------n---------tpo---------tod---------tpp---------tpk---------tnp
   1000    0.007080    0.033954    0.008131    0.009170    0.021347
   2000    0.025329    0.145372    0.025706    0.027021    0.086866
   4000    0.096382    0.541764    0.102081    0.102371    0.347644
   8000    0.414819    2.194081    0.418721    0.414379    1.401096
  16000    1.672559    8.789338    1.679220    1.675513    5.628816
-------------------------------------------------------------------
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

do podrozdziału do strony

Analizując wyniki obliczeń w arkuszu kalkulacyjnym otrzymanych czasów sortowania dla algorytmu sortowania bąbelkowego 1 wyciągamy następujące wnioski:

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

Wszystkie badane przez nas czasy sortowania są proporcjonalne do kwadratu liczby elementów zbioru. Klasa czasowej złożoności obliczeniowej wynosi O(n²).
Czasy sortowania t_po, t_pp oraz t_pk są praktycznie takie same.
Czas sortowania zbioru nieuporządkowanego jest krótszy od czasu sortowania zbioru uporządkowanego odwrotnie.

Wzrost prędkości sortowania
Algorytmy	t_po	t_od	t_pp	t_pk	t_np
Sortowanie głupie Sortowanie bąbelkowe 1	źle	dobrze	źle	źle	dobrze

Porównując wzrost prędkości algorytmu sortowania bąbelkowego w stosunku do algorytmu sortowania głupiego zauważamy, iż korzyść następuje w przypadku sortowania zbioru uporządkowanego odwrotnie oraz zbioru nieuporządkowanego. Wzrost prędkości jest proporcjonalny liniowo do liczby elementów w sortowanym zbiorze. W pozostałych przypadkach algorytm sortowania głupiego jest dużo szybszy od tej wersji algorytmu.

do podrozdziału do strony

Uzasadnij, iż wszystkie czasy dla tej wersji algorytmu są proporcjonalne do kwadratu liczby sortowanych elementów.
Dlaczego czasy t_po, t_pp oraz t_pk są takie same?
Uzasadnij wyniki otrzymane przy badaniu wzrostu prędkości algorytmu sortowania bąbelkowego 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 1
Bubble Sort

Algorytm

Uwaga:

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 1

Badania algorytmów sortowania

Podsumowanie

Zadania dla ambitnych

Sortowanie bąbelkowe - wersja nr 1 Bubble Sort

Algorytm

Uwaga:

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 1

Badania algorytmów sortowania

Podsumowanie

Zadania dla ambitnych

Sortowanie bąbelkowe - wersja nr 1
Bubble Sort