...
Algoritmi de sortare

Metoda bulelor (bubble sort), explicată pas cu pas

Pe scurt

Metoda bulelor (bubble sort) sortează o listă comparând mereu două elemente vecine și interschimbându-le când sunt în ordinea greșită. După fiecare trecere prin listă, cel mai mare element „urcă” la final, ca o bulă de aer în apă. E cel mai simplu algoritm de sortare și apare des la BAC și la primele interviuri, dar are complexitate O(n²), așa că pe liste mari e lent.

  • O(n²)pași în cel mai rău caz
  • O(n)pe o listă deja sortată, cu oprire
  • O(1)memorie în plus
  • 2lecții gratuite, fără card
METODA BULELOR 3 6 2 8 5 9 if v[j] > v[j+1]: schimbă O(n²) Python · C++

Metoda bulelor în animație

Apasă „Pornește” pe Bubble sort. Barele comparate se fac galbene, cele interschimbate roz, iar cele ajunse la locul lor verzi. Poți compara cu celelalte sortări.

Comparații 0Scrieri 0Apasă „Pornește”

Bubble sort

Compară vecinii și îi schimbă dacă sunt în ordinea greșită. După fiecare trecere, cel mai mare element ajunge la final.

Timp O(n²)Memorie O(1)

Lecția despre Bubble sort în cursul de algoritmi →
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]

Cum funcționează metoda bulelor

Iei lista de la stânga la dreapta și compari fiecare element cu vecinul lui. Dacă primul e mai mare, le interschimbi. La sfârșitul primei treceri, cel mai mare element a ajuns pe ultima poziție. Repeți pentru restul listei, iar la fiecare trecere mai fixezi un element la final.

Exemplu pe lista [5, 1, 4, 2, 8]:

TrecereaLista după trecereInterschimbăriFixat la final
1[1, 4, 2, 5, 8]3 (5↔1, 5↔4, 5↔2)8
2[1, 2, 4, 5, 8]1 (4↔2)5
3[1, 2, 4, 5, 8]0lista e sortată, ne oprim

A treia trecere nu a schimbat nimic, deci lista e sortată și algoritmul se poate opri. Asta e varianta optimizată, cu o variabilă care ține minte dacă s-a făcut vreo interschimbare.

Metoda bulelor în C++, Python, Java și pseudocod

Același algoritm, cu oprire când o trecere nu mai schimbă nimic. Codul C++ e scris ca la BAC.

def sortare_bule(v):
    n = len(v)
    for i in range(n - 1):
        schimbat = False
        for j in range(n - 1 - i):
            if v[j] > v[j + 1]:
                v[j], v[j + 1] = v[j + 1], v[j]
                schimbat = True
        if not schimbat:   # nicio interschimbare: lista e sortată
            break
    return v


print(sortare_bule([5, 1, 4, 2, 8]))   # [1, 2, 4, 5, 8]

Încearcă: scrie tu metoda bulelor în Python

Problema din lecția 78 a cursului de algoritmi: sortezi o copie a listei și numeri interschimbările. Primești verificarea pe loc.

Exercițiu din lecția 78 · cursul de algoritmi

Sortarea prin metoda bulelor și prin selecție

Scrie funcția sortare_bule(lista) care sortează crescător o copie a listei prin metoda bulelor, cu oprire timpurie, și returnează tuplul (lista_sortata, interschimbari), unde interschimbari este numărul total de interschimbări făcute. Nu folosi sort() sau sorted().

  1. Fă o copie: a = lista[:].
  2. Pentru fiecare trecere, compară vecinii și interschimbă-i când a[j] > a[j + 1], numărând interschimbările.
  3. Oprește-te când o trecere nu schimbă nimic. Trebuie să apară: ([1, 2, 4, 5, 8], 4), ([1, 2, 3], 0), ([1, 2, 3], 3), ([], 0).
Indiciu: Interschimbarea în Python: a[j], a[j + 1] = a[j + 1], a[j].
def sortare_bule(lista):
    a = lista[:]
    n = len(a)
    interschimbari = 0
    for trecere in range(n - 1):
        schimbat = False
        for j in range(n - 1 - trecere):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                interschimbari += 1
                schimbat = True
        if not schimbat:
            break
    return a, interschimbari


print(sortare_bule([5, 1, 4, 2, 8]))
print(sortare_bule([1, 2, 3]))
print(sortare_bule([3, 2, 1]))
print(sortare_bule([]))
Începe gratuit cursul de algoritmi →
main.pyPython
ConsolăGata de pornire
Apasă „Rulează codul”. Prima dată Python se încarcă în browser în câteva secunde.

Pe tema asta, în cursul de algoritmi

Pagina îți arată metoda. În curs o aplici singur, pe probleme din ce în ce mai grele, cu verificare automată la fiecare.

Complexitatea metodei bulelor

CazComplexitateCând apare
Cel mai răuO(n²)lista e sortată invers: fiecare comparație duce la o interschimbare
MediuO(n²)elemente în ordine aleatoare
Cel mai bunO(n)lista e deja sortată și folosești varianta cu oprire
MemorieO(1)sortează pe loc, fără listă nouă

Pentru n = 10.000 de elemente înseamnă aproximativ 50 de milioane de comparații. De aceea, în practică se folosesc sortări O(n log n), ca merge sort sau quicksort, sau direct sort() din C++ și sorted() din Python. Metoda bulelor e stabilă: elementele egale își păstrează ordinea.

Metoda bulelor la BAC

La BAC Informatică metoda bulelor apare în două forme: în pseudocod, la Subiectul I sau II, unde trebuie să spui ce afișează algoritmul sau câte interschimbări face, și în C++, la Subiectul III, unde sortezi un vector (crescător, descrescător sau după un criteriu, de exemplu după suma cifrelor). Pentru ordine descrescătoare schimbi doar semnul comparației: v[j] < v[j + 1].

Greșeala cea mai des întâlnită: bucla interioară merge până la n - 1 inclusiv și citește v[n], în afara vectorului. Vezi și regulile pseudocodului.

4,9 din 5 · 128 de recenzii Google

Ce spun cursanții

Toate recenziile pe Google
Video · 13 minute

Absolvenții noștri, în cuvintele lor

Cursanți care au pornit de la zero povestesc cum au învățat, ce i-a ajutat și unde au ajuns după cursuri.

Vezi pe YouTube

Am terminat cursul de C# incepatori si ma declar foarte multumita de acesta. Trainerul, Gabriel, a fost super ok si ne-a ajutat sa intelegem atunci cand aveam intrebari. Materia a fost foarte bine prezentata si parcursa foarte mult prin exercitii practice. Clar voi reveni si pentru cursul de intermediari!

Fotografia lui Mihaela Dumitru, cursant al Academiei ProgramatorilorMihaela DumitruRecenzie pe Google

La cursul de Java am avut placerea sa acumulez o multitudine de informatii foarte utile pentru a imi incepe drumul de programator de la trainerul Gabriel, un trainer vizibil foarte pasionat de ceea ce face, rabdator cu elevii sai si dornic sa ne dezvolte pe partea profesionala. Astept cu nerabdare urmatorul curs!!

Fotografia lui Bea Danciu, cursant al Academiei ProgramatorilorBea DanciuRecenzie pe Google

Recomand cursul online de programare, foarte bine structurat, explicatiile sunt usor de inteles si contine foarte multe exercitii practice.

Fotografia lui Ioana Dumitrache, cursant al Academiei ProgramatorilorIoana DumitracheRecenzie pe Google

Întrebări frecvente

Ce este metoda bulelor?

Metoda bulelor (bubble sort) este un algoritm de sortare care compară repetat elementele vecine dintr-o listă și le interschimbă dacă sunt în ordinea greșită. După fiecare trecere, cel mai mare element ajunge la sfârșitul listei, ca o bulă care urcă la suprafață.

Care este complexitatea metodei bulelor?

O(n²) în cazul mediu și în cel mai rău caz, pentru că face aproximativ n²/2 comparații. În varianta cu oprire, pe o listă deja sortată face o singură trecere, deci O(n). Memoria suplimentară este O(1).

Care e diferența dintre metoda bulelor și sortarea prin selecție?

Metoda bulelor interschimbă vecinii de fiecare dată când sunt în ordine greșită, deci poate face multe interschimbări. Sortarea prin selecție caută minimul din partea nesortată și face o singură interschimbare pe trecere. Ambele au O(n²).

Cum sortez descrescător cu metoda bulelor?

Schimbi doar condiția de comparație: interschimbi când v[j] < v[j + 1], în loc de v[j] > v[j + 1]. Restul algoritmului rămâne la fel.

Se folosește metoda bulelor în practică?

Rar. Pe liste mari este mult mai lentă decât merge sort sau quicksort. Se învață pentru că e simplă și arată clar ideea de sortare și de complexitate, iar la BAC și la interviuri ți se poate cere să o scrii sau să o analizezi.

Unde exersez metoda bulelor?

În cursul de algoritmi pentru interviuri de la Academia Programatorilor, lecția „Sortarea prin metoda bulelor și prin selecție”, unde scrii codul în Python direct în browser și primești verificare automată. Primele 2 lecții ale cursului sunt gratuite.

Începe azi, gratuit

Primele lecții din fiecare curs sunt gratuite. Fără card, fără instalări: scrii primul cod în câteva minute.