De ce contează?
Ții în mână un teanc de cărți de joc neordonate. Nu vrei să te gândești prea mult: te uiți doar la două cărți vecine și, dacă cea din stânga e mai mare, le inversezi. Mergi de la un capăt la altul, iar și iar, până când nu mai ai ce schimba. Cardul cel mai mare „urcă” singur la coadă de fiecare dată — exact ca o bulă de aer care iese la suprafață. Asta e tot Bubble Sort.
Ce este Bubble Sort?
Bubble Sort este cel mai simplu algoritm de sortare prin comparație. La fiecare trecere prin șir, elementele mai mari „plutesc” (bubble) spre dreapta, la fel cum bulele de aer urcă în apă.
De ce să-l înveți, dacă în concurs vei folosi oricum std::sort? Pentru că
Bubble Sort e cel mai clar exemplu prin care înțelegi două idei pe care le vei
reîntâlni la orice algoritm de sortare: o comparație decide o singură
inversiune locală, iar repetarea acestor decizii locale aduce, pas cu pas,
ordinea globală. Cine pricepe asta nu mai memorează coduri de sortare — le
deduce.