Metoda bulelor (în engleză Bubble Sort) este probabil primul algoritm de sortare pe care l-ai învățat. La BAC informatică apare în mai multe forme: ca secvență de cod de completat, ca algoritm în pseudocod pe care trebuie să-l urmărești („ce valori are vectorul după prima parcurgere?”) sau ca parte dintr-un program în care trebuie să ordonezi niște valori. E simplă, dar are câteva detalii care fac diferența între un răspuns corect și unul greșit.

Ideea metodei bulelor

Parcurgi vectorul de la stânga la dreapta și compari fiecare element cu vecinul lui din dreapta. Dacă sunt în ordinea greșită (primul e mai mare, pentru o sortare crescătoare), le interschimbi. La sfârșitul unei parcurgeri, cel mai mare element a „urcat” ca o bulă până pe ultima poziție. Repeți parcurgerile până când nu mai faci nicio interschimbare — semn că vectorul e sortat.

Urmărirea pas cu pas

Să sortăm crescător vectorul 5 3 8 1 (n = 4). Fiecare rând arată o comparație între două elemente vecine și vectorul după ea:

ParcurgereaComparațieInterschimbare?Vectorul
15 cu 3da3 5 8 1
15 cu 8nu3 5 8 1
18 cu 1da3 5 1 8
23 cu 5nu3 5 1 8
25 cu 1da3 1 5 8
25 cu 8nu3 1 5 8
33 cu 1da1 3 5 8
33 cu 5nu1 3 5 8
35 cu 8nu1 3 5 8
43 comparațiiniciuna1 3 5 8

Observă două lucruri. După prima parcurgere, 8 (maximul) e deja pe ultima poziție; după a doua, 5 e pe penultima. Și a fost nevoie de o parcurgere în plus (a patra), fără nicio interschimbare, ca algoritmul să „afle” că vectorul e sortat. În total s-au făcut 4 interschimbări — exact numărul de perechi aflate inițial în ordine greșită: (5,3), (5,1), (3,1), (8,1).

Codul C++: varianta cu indicator

Cea mai folosită variantă păstrează o variabilă sortat, care rămâne 1 doar dacă o parcurgere întreagă nu a făcut nicio interschimbare:

#include <iostream>
using namespace std;

int main()
{
    int n, v[101], i, aux, sortat;
    cin >> n;
    for (i = 1; i <= n; i++) cin >> v[i];
    do
    {
        sortat = 1;
        for (i = 1; i < n; i++)
            if (v[i] > v[i + 1])
            {
                aux = v[i];
                v[i] = v[i + 1];
                v[i + 1] = aux;
                sortat = 0;
            }
    } while (sortat == 0);
    for (i = 1; i <= n; i++) cout << v[i] << ' ';
    return 0;
}

Atenție la limita buclei interioare: i < n, nu i <= n. Altfel, la ultimul pas compari v[n] cu v[n + 1], un element care nu face parte din vector. Este una dintre cele mai frecvente greșeli la completarea codului.

Varianta optimizată

Ai văzut că după fiecare parcurgere încă un element ajunge definitiv la locul lui, la final. Nu mai are rost să-l comparăm. Putem micșora la fiecare pas zona parcursă:

int dr = n, sortat;
do
{
    sortat = 1;
    for (i = 1; i < dr; i++)
        if (v[i] > v[i + 1])
        {
            aux = v[i]; v[i] = v[i + 1]; v[i + 1] = aux;
            sortat = 0;
        }
    dr--;
} while (sortat == 0);

Pe exemplul nostru, parcurgerile fac acum 3, 2 și 1 comparații (a patra nu mai are nimic de comparat), adică 6 în total, față de 3 + 3 + 3 + 3 = 12 în varianta simplă. În cel mai rău caz (vector ordonat descrescător), ambele variante fac un număr de comparații proporțional cu n², iar cea optimizată face exact n(n−1)/2. În cel mai bun caz (vector deja sortat), o singură parcurgere de n−1 comparații e suficientă.

Metoda bulelor în pseudocod

În subiectele de BAC, algoritmul poate apărea și în pseudocod, cu structura repetă…până când:

citește n, v[1], v[2], …, v[n]
repetă
    ok ← 1
    pentru i ← 1, n-1 execută
        dacă v[i] > v[i+1] atunci
            aux ← v[i]; v[i] ← v[i+1]; v[i+1] ← aux
            ok ← 0
până când ok = 1

Sortări după alte criterii

Schimbând doar condiția din if, sortezi după orice criteriu:

Metoda bulelor este stabilă: elementele „egale” după criteriu își păstrează ordinea relativă inițială, pentru că interschimbi doar la inegalitate strictă. Dacă scrii >= în loc de >, pierzi această proprietate și, cu varianta cu indicator, bucla nu se mai termină dacă există două valori egale.

La BAC: la întrebări de tipul „câte interschimbări se efectuează?”, nu trebuie să simulezi tot algoritmul. Numărul de interschimbări la metoda bulelor este egal cu numărul de perechi (i, j), cu i < j, pentru care v[i] > v[j]. Numără perechile — e mai rapid și mai sigur.

Când o folosești și când nu

Metoda bulelor e potrivită pentru vectori mici (zeci sau câteva sute de elemente) și pentru itemii în care se cere explicit. La problema de eficiență din Subiectul III, unde pot fi un milion de valori, o sortare pătratică nu e o soluție eficientă — acolo cauți un vector de frecvență sau o prelucrare din mers.

De reținut