Bubble Sort — AlgoClar

De ce contează?

Ai o coloană de baloane cu greutăți diferite. La fiecare pas, compari baloanele vecine: dacă cel din stânga e mai greu, le schimbi locurile. Cel mai greu „plutește" spre dreapta. Repeți până când niciun balon nu mai trebuie mutat.

Cum funcționează Bubble Sort?

La fiecare trecere, parcurgem vectorul și comparăm elementele vecine. Dacă sunt în ordine greșită, le schimbăm. Cel mai mare element „burbuiește" spre dreapta și ajunge pe locul lui final.

O trecere pe v = {5, 3, 8, 1, 9}:

(5,3) → swap → {3, 5, 8, 1, 9}
(5,8) → ok
(8,1) → swap → {3, 5, 1, 8, 9}
(8,9) → ok

După prima trecere: 9 e pe locul final. Repetăm pentru restul.

Implementare C++

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    int v[1001];
    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 t = v[j]; v[j] = v[j+1]; v[j+1] = t;
            }
        }
    }

    for (int i = 0; i < n; i++) cout << v[i] << " ";
    return 0;
}

Versiunea optimizată

Dacă o trecere completă nu produce niciun swap, vectorul e deja sortat — nu mai continuăm:

for (int i = 0; i < n - 1; i++) {
    bool swapped = false;
    for (int j = 0; j < n - 1 - i; j++) {
        if (v[j] > v[j + 1]) {
            int t = v[j]; v[j] = v[j+1]; v[j+1] = t;
            swapped = true;
        }
    }
    if (!swapped) break;    // niciun swap = deja sortat
}

Complexitate

Caz	Timp
Cel mai bun (cu opt., deja sortat)	O(n)
Mediu / Cel mai rău	O(n²)

Observația-cheie

Fără optimizare, Bubble Sort face mereu O(n²), chiar pe date sortate. Cu flagul swapped, se oprește după o singură trecere pe date deja sortate — O(n). Adăugarea flagului nu costă nimic și poate economisi mult timp.

Vizualizare

Indiciu

Urmărește bulele mari deplasându-se spre dreapta la fiecare trecere. Zona din dreapta marchează elementele deja pe pozițiile finale — zona de lucru se micșorează cu fiecare trecere.

Greșeli frecvente

Greșeala 1: Bucla interioară merge până la j < n în loc de j < n-1-i — accesezi v[n], care e în afara vectorului.

Greșeala 2: Nu reduci limita buclei interioare cu -i — recomparăm elementele deja sortate la fiecare trecere (corect, dar ineficient).

Greșeala 3: Swap fără variabilă temporară: v[j] = v[j+1]; v[j+1] = v[j]; — prima valoare se pierde înainte de a fi salvată.

Recapitulare

Bubble Sort compară perechi vecine și face swap dacă sunt în ordine greșită.
O(n²) în general; O(n) pe date sortate cu varianta optimizată.
Nu se folosește la concursuri pentru n > 10.000 — prea lent.