Sortarea prin metoda bulelor

Metoda bulelor compară perechi vecine și le schimbă dacă sunt în ordine greșită. După o parcurgere completă pentru sortare crescătoare, cel mai mare element din zona parcursă ajunge la capătul din dreapta. Din $[5,2,4]$, schimburile dau $[2,5,4]$ și apoi $[2,4,5]$.

În Python, după v=[5,2], atribuirea v[0],v[1]=v[1],v[0] schimbă vecinii aflați în ordine greșită; lista devine [2,5].

O trecere prin vector

Parcurgi vectorul de la stânga la dreapta și compari fiecare element cu vecinul lui din dreapta. Dacă primul e mai mare, îi interschimbi. Cel mai mare element, oriunde ar fi, câștigă toate comparațiile din dreapta lui, deci este împins până pe ultima poziție. A doua trecere face același lucru pentru al doilea cel mai mare element și așa mai departe. De aceea trecerea i se poate opri cu i poziții înainte de final: acolo valorile sunt deja la locul lor.

citește n, v[0], v[1], …, v[n-1] (numere întregi)
┌pentru i ← 0, n-2 execută
│ ┌pentru j ← 0, n-2-i execută
│ │ ┌dacă v[j] > v[j+1] atunci
│ │ │  aux ← v[j]; v[j] ← v[j+1]; v[j+1] ← aux
│ │ └■
│ └■
└■

Varianta cu oprire anticipată

Dacă la o trecere nu s-a făcut nicio interschimbare, vectorul este deja sortat și restul trecerilor nu mai schimbă nimic. O variabilă sortat reține acest lucru: o pui pe 1 la începutul trecerii și o faci 0 la fiecare interschimbare. Pe un vector deja sortat, varianta face o singură trecere; în cel mai rău caz, la fel de multe comparații ca varianta clasică.

void bule(int v[], int n) {
    int sortat;
    do {
        sortat = 1;
        for (int j = 0; j < n - 1; j++)
            if (v[j] > v[j + 1]) {
                int aux = v[j];
                v[j] = v[j + 1];
                v[j + 1] = aux;
                sortat = 0;          // a avut loc o interschimbare
            }
        n--;                         // ultimul element e la locul lui
    } while (sortat == 0);
}

Parametrul n este transmis prin valoare, deci scăderea lui în subprogram nu modifică variabila din apel; tabloul v este însă modificat, pentru că un tablou transmis ca parametru lucrează pe elementele originale.

Cât de rapidă este

Varianta clasică face (n − 1) + (n − 2) + … + 1 = n(n − 1)/2 comparații; pentru 1 000 de elemente, 499 500. Numărul de operații crește cu pătratul lui n (ordinul $n^2$), de aceea metoda se folosește pentru vectori mici sau aproape sortați. Pentru vectori mari, sortarea prin interclasare face de ordinul $n\log n$ operații, iar quicksort la fel, în medie. Comparația cu celelalte metode din programă este în capitolul Sortare.

În Python (clasa a IX-a, programa nouă)

Programa nouă de clasa a IX-a numește explicit metoda bulelor, iar vectorul este o listă Python:

v = [5, 2, 8, 1, 4]
n = len(v)
for i in range(n - 1):
    for j in range(n - 1 - i):
        if v[j] > v[j + 1]:
            v[j], v[j + 1] = v[j + 1], v[j]
print(v)

[1, 2, 4, 5, 8]

Un exemplu cu trei elemente

#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int v[] = {5, 2, 4, 1, 3}, n = 5;
    for (int capat = n - 1; capat > 0; --capat) {
        for (int j = 0; j < capat; ++j)
            if (v[j] > v[j + 1])
                swap(v[j], v[j + 1]);
        for (int x : v) cout << x << ' ';
        cout << '\n';
    }
    return 0;
}

După prima trecere tabloul este 2 4 1 3 5: valoarea 5 a urcat până la capăt prin patru schimburi consecutive. După a doua trecere este 2 1 3 4 5, după a treia 1 2 3 4 5, iar a patra trecere nu mai schimbă nimic. În total sunt 10 comparații și 7 schimburi, egal cu numărul inversiunilor lui $5,2,4,1,3$.

Exemplul 2 — oprirea timpurie. Dacă o trecere nu face niciun schimb, tabloul este sortat și algoritmul se poate opri. Pentru $1,2,3,5,4$ prima trecere schimbă doar perechea $(5;4)$, iar a doua trecere nu schimbă nimic: sunt 2 treceri și $2\cdot 4=8$ comparații, față de 10 în varianta fără oprire. Un indicator logic schimbat, pus pe fals la începutul fiecărei treceri și pe adevărat la fiecare schimb, decide dacă se mai face o trecere.

bool schimbat;
do {
    schimbat = false;
    for (int j = 0; j < n - 1; ++j)
        if (v[j] > v[j + 1]) {
            swap(v[j], v[j + 1]);
            schimbat = true;
        }
} while (schimbat);

Pentru un tablou deja sortat, această variantă face o singură trecere și $n-1$ comparații, deci este liniară.

Exemplul 3 — ce garantează o trecere. Pentru tabloul $3,1,4,1,5,9,2$, o singură trecere dă 1 3 1 4 5 2 9, cu 3 schimburi: 3 trece peste 1, 4 peste 1, iar 9 se mută până la capăt, trecând peste 2. Doar ultimul element, 9, este garantat pe locul lui; restul tabloului nu este încă sortat. Nu poți presupune că după o trecere primele elemente sunt în ordine. Elementele mici se deplasează spre stânga doar câte o poziție pe trecere, de aceea o valoare mică aflată la capătul din dreapta cere multe treceri.

Exemplul 4 — cazul cel mai nefavorabil și invariantul. Un tablou ordonat descrescător, $4,3,2,1$, are toate perechile în ordine greșită: $\frac{4\cdot 3}{2}=6$ inversiuni. Trecerile dau 3 2 1 4, 2 1 3 4 și 1 2 3 4, cu 3, 2 și 1 schimburi: în total 6 schimburi, câte unul pentru fiecare comparație. La un tablou descrescător metoda bulelor face deci numărul maxim de schimburi, iar timpul ei este proporțional cu $n^2$. Invariantul algoritmului: după $k$ treceri, ultimele $k$ elemente ale tabloului sunt cele mai mari $k$ valori, așezate crescător și aflate pe locul lor definitiv. De aceea trecerea următoare poate să se oprească înaintea lor, iar după $n-1$ treceri tabloul este sortat.

Exemple rezolvate

Exemplul 1: trecerile, pas cu pas

Sortează crescător vectorul 5, 2, 8, 1, 4 și afișează-l după fiecare trecere.

1. Trecerea 1: (5, 2) se interschimbă, (5, 8) rămân, (8, 1) și (8, 4) se interschimbă: 2, 5, 1, 4, 8. Valoarea 8 e la locul ei.
2. Trecerea 2: (2, 5) rămân, (5, 1) și (5, 4) se interschimbă: 2, 1, 4, 5, 8.
3. Trecerea 3: (2, 1) se interschimbă: 1, 2, 4, 5, 8.
4. Trecerea 4: nicio interschimbare.

#include <iostream>
using namespace std;

int main() {
    int v[] = {5, 2, 8, 1, 4}, n = 5;
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - 1 - i; j++)
            if (v[j] > v[j + 1]) {
                int aux = v[j];
                v[j] = v[j + 1];
                v[j + 1] = aux;
            }
        for (int k = 0; k < n; k++)
            cout << v[k] << " ";
        cout << "\n";
    }
    return 0;
}

Programul afișează:

2 5 1 4 8
2 1 4 5 8
1 2 4 5 8
1 2 4 5 8

Exemplul 2: numărul de interschimbări

Câte interschimbări face metoda bulelor pentru vectorul din exemplul 1?

1. Din pașii de mai sus: 3 interschimbări la prima trecere, 2 la a doua, 1 la a treia: 6 în total.
2. Altă cale: numeri inversiunile, perechile de valori în care cea mai mare stă înaintea celei mai mici: (5, 2), (5, 1), (5, 4), (2, 1), (8, 1), (8, 4). Sunt 6, pentru că fiecare interschimbare de vecini elimină exact o inversiune.

#include <iostream>
using namespace std;

int main() {
    int n, v[100], nr = 0;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> v[i];
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (v[j] > v[j + 1]) {
                int aux = v[j]; v[j] = v[j + 1]; v[j + 1] = aux;
                nr++;
            }
    cout << nr << "\n";
    return 0;
}

Pentru intrarea 5 și 5 2 8 1 4, programul afișează:

6

Pentru vectorul 10, 9, 8, …, 1 afișează 45 = 10 · 9 / 2: fiecare pereche este o inversiune.

Exemplul 3: câte treceri face varianta cu oprire anticipată

Pentru vectorul 1, 2, 3, 5, 4, câte treceri face varianta cu variabila sortat?

1. Trecerea 1: singura interschimbare este (5, 4), deci sortat devine 0 și algoritmul continuă.
2. Trecerea 2: nicio interschimbare, sortat rămâne 1, algoritmul se oprește.
3. Răspunsul: 2 treceri. Varianta clasică ar fi făcut toate cele 4 treceri.

Exemplul 4: sortarea după un criteriu

Ordonează numerele 123, 45, 9, 300, 18, 72 descrescător după suma cifrelor, iar la sumă egală, crescător după valoare.

1. Sumele cifrelor: 6, 9, 9, 3, 9, 9.
2. Două numere a și b, cu a înaintea lui b, sunt în ordine greșită dacă suma cifrelor lui a este mai mică sau dacă sumele sunt egale și a > b. Aceasta este condiția de interschimbare.

#include <iostream>
using namespace std;

int suma(int x) {
    int s = 0;
    while (x > 0) {
        s = s + x % 10;
        x = x / 10;
    }
    return s;
}

int main() {
    int v[] = {123, 45, 9, 300, 18, 72}, n = 6;
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++) {
            int sa = suma(v[j]), sb = suma(v[j + 1]);
            if (sa < sb || (sa == sb && v[j] > v[j + 1])) {
                int aux = v[j]; v[j] = v[j + 1]; v[j + 1] = aux;
            }
        }
    for (int k = 0; k < n; k++)
        cout << v[k] << " ";
    cout << "\n";
    return 0;
}

Programul afișează:

9 18 45 72 123 300

Exemplul 5: nivel de examen, sortarea doar pe pozițiile pare

Vectorul are elementele 9, 8, 7, 6, 5, 4, 3, 2, pe pozițiile de la 1 la 8. Ordonează crescător numai elementele de pe pozițiile pare, fără să le muți pe celelalte.

1. Elementele de pe pozițiile 2, 4, 6, 8 sunt 8, 6, 4, 2; ordonate, devin 2, 4, 6, 8.
2. Metoda bulelor se aplică pe „vecinii” din subșirul pozițiilor pare: compari v[j] cu v[j + 2], pentru j = 2, 4, 6.
3. Rezultatul: 9, 2, 7, 4, 5, 6, 3, 8.

#include <iostream>
using namespace std;

int main() {
    int v[9] = {0, 9, 8, 7, 6, 5, 4, 3, 2}, n = 8;   // pozitiile 1..8
    int sortat;
    do {
        sortat = 1;
        for (int j = 2; j + 2 <= n; j = j + 2)
            if (v[j] > v[j + 2]) {
                int aux = v[j]; v[j] = v[j + 2]; v[j + 2] = aux;
                sortat = 0;
            }
    } while (sortat == 0);
    for (int k = 1; k <= n; k++)
        cout << v[k] << " ";
    cout << "\n";
    return 0;
}

Programul afișează:

9 2 7 4 5 6 3 8

La urmărire, distinge trecerile complete de schimburile individuale. După o trecere, numai ultimul element al zonei active este garantat pe locul definitiv. Dacă în cod apare condiția >=, valorile egale pot fi schimbate și stabilitatea nu mai este garantată. Dacă un subiect cere numărul de schimburi, numără inversiunile; dacă cere numărul de comparații fără oprire timpurie, el nu depinde de valori.

Exemplu în formatul examenului. Ce se afișează în urma executării secvenței de mai jos?

int v[] = {3, 1, 4, 1, 5, 9, 2}, n = 7, sw = 0;
for (int j = 0; j < n - 1; j++)
    if (v[j] > v[j + 1]) {
        swap(v[j], v[j + 1]);
        sw++;
    }
for (int j = 0; j < n; j++)
    cout << v[j] << ' ';
cout << sw;

• a) 1 1 2 3 4 5 9 3
• b) 1 3 1 4 5 2 9 3
• c) 1 3 1 4 5 9 2 2
• d) 3 1 4 1 5 2 9 1

Răspunsul corect este b). Secvența este o singură trecere. Se compară $(3;1)$ și se schimbă ($sw=1$): 1 3 4 1 5 9 2. Se compară $(3;4)$, nu se schimbă. Se compară $(4;1)$ și se schimbă ($sw=2$): 1 3 1 4 5 9 2. Perechile $(4;5)$ și $(5;9)$ nu se schimbă. Se compară $(9;2)$ și se schimbă ($sw=3$): 1 3 1 4 5 2 9. Varianta a) este tabloul sortat complet, care ar cere mai multe treceri.

Al doilea exemplu în formatul examenului. Ce se afișează în urma executării secvenței de mai jos?

int v[] = {3, 4, 5, 2, 1}, n = 5, sw = 0;
for (int i = 0; i < 2; i++)
    for (int j = 0; j < n - 1 - i; j++)
        if (v[j] > v[j + 1]) {
            swap(v[j], v[j + 1]);
            sw++;
        }
for (int j = 0; j < n; j++)
    cout << v[j] << ' ';
cout << sw;

• a) 1 2 3 4 5 4
• b) 3 2 1 4 5 4
• c) 3 4 2 1 5 2
• d) 3 2 1 4 5 7

Răspunsul corect este b). Ciclul exterior face doar două treceri. În prima, perechile $(3;4)$ și $(4;5)$ rămân, apoi $(5;2)$ și $(5;1)$ se schimbă: 3 4 2 1 5, cu 2 schimburi. În a doua trecere, care se oprește înaintea lui 5, $(3;4)$ rămâne, iar $(4;2)$ și $(4;1)$ se schimbă: 3 2 1 4 5, cu încă 2 schimburi, deci $sw=4$. Varianta a) este tabloul sortat complet, iar varianta c) se oprește după prima trecere.

Unde apare la examen

• Bacalaureatul, informatică, matematică-informatică: programa de examen numește explicit „metoda bulelor”, alături de inserție, selecție și numărare, la metodele de ordonare, precum și analiza complexității unui algoritm (programa de examen, anexa 2 la OMECTS 4800/2010). Formatul probei și subiectele din 2026 sunt pe pagina subiectelor și baremelor Bac 2026; potrivit proiectului de ordin pentru Bacalaureatul 2027, programa rămâne aceeași.
• Programa școlară: pe programa veche, sortarea este la clasa a X-a, la algoritmii de prelucrare a tablourilor (programa de clasa a X-a, OMECI 5099/2009); programa nouă de clasa a IX-a cere caracteristicile metodei bulelor și aplicarea ei, alături de selecția minimului și de sortarea cu listă de frecvențe (OMEC 6930/2025, anexa 42).

Greșeli frecvente

• Greșit: după o trecere, tabloul este sortat.
  Corect: după o trecere doar cel mai mare element al zonei active este pe locul lui.
• Greșit: metoda bulelor compară mereu elementele aflate la distanță.
  Corect: compară numai elemente vecine.
• Greșit: cu condiția >= valorile egale rămân în ordinea inițială.
  Corect: ele se pot schimba între ele, deci stabilitatea nu mai este garantată.
• Greșit: bucla interioară merge cu j < n.
  Corect: compară v[j] cu v[j + 1], deci j merge până la n − 2 (condiția j < n - 1); cu j < n, ultima comparație citește v[n], care nu face parte din vector.
• Greșit: interschimbarea v[j] = v[j + 1]; v[j + 1] = v[j];.
  Corect: pune aceeași valoare în ambele poziții, deci ai nevoie de variabila auxiliară aux.
• Greșit: comparația v[j] >= v[j + 1].
  Corect: elementele egale se interschimbă inutil, iar metoda nu mai este stabilă; folosești >.
• Greșit: variabila sortat se inițializează o singură dată.
  Corect: se pune pe 1 la începutul fiecărei treceri; altfel, după prima interschimbare rămâne 0 pentru totdeauna, iar bucla nu se mai oprește.
• Greșit: metoda bulelor se confundă cu sortarea prin selecție.
  Corect: la selecție cauți minimul și îl muți direct pe poziția lui; la metoda bulelor compari doar vecini.
• Greșit: se compară orice două elemente, chiar dacă nu sunt vecine.
  Corect: varianta de bază compară vecini.
• Greșit: după o singură trecere tot tabloul este garantat sortat.
  Corect: este fixat doar capătul zonei active.
• Greșit: indicele j+1 este valid și la j=n-1.
  Corect: bucla trebuie să se oprească înainte.

Înainte și după

Întrebări frecvente