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.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- da
- da
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ă
Î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ă.