Sortarea prin metoda bulelor
Metoda bulelor (bubble sort) este cel mai simplu algoritm de sortare de descris: comparați doi vecini, interschimbați-i dacă sunt în ordine greșită și repetați. Este lentă pe liste lungi, dar fiecare pas e ușor de urmărit, de aceea e algoritmul clasic cu care se începe.
Ideea
Parcurgeți lista de la stânga la dreapta și priviți fiecare pereche de vecini. Dacă valoarea din stânga e mai mare decât cea din dreapta, interschimbați-le. Când ajungeți la capăt, cea mai mare valoare a fost dusă până pe ultimul loc, așa cum o bulă urcă la suprafață. Această parcurgere se numește trecere. Repetați trecerile până când lista e sortată.
Un exemplu
Luăm 5, 1, 4, 2, 8. Prima trecere compară 5 și 1 și le interschimbă, apoi 5 și 4 (interschimbare), 5 și 2 (interschimbare) și 5 și 8 (fără interschimbare): 1, 4, 2, 5, 8. 8 este acum pe locul final. A doua trecere compară 1 și 4 (fără interschimbare), 4 și 2 (interschimbare) și 4 și 5 (fără interschimbare): 1, 2, 4, 5, 8. A treia trecere nu face nicio interschimbare, deci lista e sortată: 9 comparații și 4 interschimbări.
De ce fiecare trecere mai fixează o valoare
În timpul unei treceri, cea mai mare valoare întâlnită până atunci este mereu dusă mai departe: odată ce trecerea ajunge la ea, fiecare comparație o mută cu o poziție la dreapta. Astfel, prima trecere pune cea mai mare valoare ultima, a doua pune a doua cea mai mare chiar înaintea ei și așa mai departe. După trecerea k, ultimele k poziții sunt finale, iar următoarea trecere se poate opri cu o poziție mai devreme. De aceea trecerile devin tot mai scurte.
Interschimbările egalează inversiunile
O inversiune este o pereche de valori aflate în ordine greșită: o valoare mai mare undeva înaintea uneia mai mici. Interschimbarea a doi vecini aflați în ordine greșită elimină exact o inversiune și nu creează niciuna nouă. Așadar metoda bulelor face exact atâtea interschimbări câte inversiuni are lista inițială, indiferent în ce ordine vin comparațiile. O listă sortată nu are niciuna; o listă inversată de n valori are n(n − 1)/2, maximul posibil.
Oprirea timpurie și costul
Dacă o trecere întreagă nu face nicio interschimbare, toți vecinii sunt în ordine și lista e sortată. Această verificare permite metodei bulelor să termine o listă sortată într-o singură trecere de n − 1 comparații. În cel mai rău caz tot e nevoie de n − 1 treceri și n(n − 1)/2 comparații, iar în medie numărul de interschimbări este n(n − 1)/4. Ambele cresc cu n², deci dublarea listei face sortarea de aproximativ patru ori mai lungă.
Metoda bulelor este stabilă: valorile egale nu se interschimbă niciodată, deci își păstrează ordinea. Sortează pe loc, fără memorie suplimentară. Sortarea prin inserție are aceleași proprietăți și de obicei necesită mai puțini pași, iar sortarea prin interclasare și quicksort durează un timp proporțional cu n log n, mult mai puțin pe liste lungi.
Explorați
Deschideți aplicația și apăsați Redare sau apăsați Pas ca să avansați câte o comparație. Cele două valori comparate sunt evidențiate, o interschimbare apare în culoarea ei, iar valorile deja la locul lor devin verzi. Încercați o listă inversată ca să vedeți cel mai rău caz, una aproape sortată ca să vedeți cum oprirea timpurie încheie sortarea după câteva treceri, sau introduceți numerele din exemplul de mai sus.
Întrebări frecvente
Care este complexitatea în timp a metodei bulelor?
O(n²) în cazul cel mai rău și în cel mediu: până la n(n − 1)/2 comparații pentru n valori. Cu oprirea timpurie, o listă deja sortată necesită O(n), o singură trecere. Are nevoie doar de O(1) memorie suplimentară.
Este metoda bulelor stabilă?
Da. Interschimbă doi vecini doar când cel din stânga e strict mai mare, așa că valorile egale nu trec niciodată una de alta și își păstrează ordinea inițială.
Care e diferența dintre metoda bulelor și sortarea prin inserție?
Ambele interschimbă vecini și ambele fac atâtea interschimbări câte inversiuni există. Metoda bulelor face treceri complete peste partea nesortată; sortarea prin inserție mută fiecare valoare nouă înapoi doar cât e nevoie, deci de obicei face mai puține comparații, mai ales pe liste aproape sortate.
Când este metoda bulelor o alegere bună?
Mai ales în predare și pentru liste foarte scurte, unde simplitatea contează mai mult decât viteza. Pentru orice mai mare, sortarea încorporată în limbajul dvs. de programare este mult mai rapidă.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați metoda bulelor