Sortare prin bule

Parcurge lista de mai multe ori și schimbă între ei vecinii aflați în ordine greșită. După fiecare trecere, cea mai mare valoare rămasă ajunge la capăt.

cel mai bun caz Ω(n)
caz mediu Θ(n²)
cel mai rău caz O(n²)
memorie O(1)
stabil
fără memorie suplimentară

Ce înseamnă acești termeni?

Cel mai bun caz: cum crește timpul cu mărimea n a listei când intrarea e cea mai ușoară pentru acest algoritm.
Caz mediu: creșterea obișnuită a timpului. La n², de două ori mai multe valori cer cam de patru ori mai mult timp; n log n crește mai lent.
Cel mai rău caz: creșterea pe intrarea cea mai grea. Util când viteza nu are voie să scadă niciodată.
Memorie: câtă memorie suplimentară e necesară pe lângă listă. 1 înseamnă câteva variabile, n înseamnă o copie a listei.
Stabil: două valori egale își păstrează ordinea inițială. Contează când sortezi după un singur câmp al unei înregistrări.
Fără memorie suplimentară: sortează chiar în listă, fără o a doua listă.

comparare
mutare
pe poziția finală

0 / 453 pași

Comparații Schimbări

Apasă pe redare: liniile arată cum crește costul în timpul sortării

Viteză 8 pași/s

Space: redă sau pauză. Săgețile stânga și dreapta: pas cu pas. Home și End: salt.

Încearcă: Alege o listă aproape sortată. După o trecere fără nicio schimbare, algoritmul se oprește mai devreme.

Cum funcționează

Compară câte doi vecini și îi schimbă între ei dacă cel din stânga e mai mare. Așa, la fiecare trecere, cea mai mare valoare ajunge tocmai în dreapta, ca o bulă care urcă. Dacă o trecere nu face nicio schimbare, lista e deja sortată.

Când este o alegere bună

Aproape niciodată în programe reale, pentru că e lent pe liste lungi. E foarte bun pentru învățat: arată ideea de bază a sortării prin comparare și schimbare. E rapid doar când lista e deja sortată.