Quicksort
Alege o valoare, pivotul, și mută valorile mai mici în stânga lui și pe cele mai mari în dreapta. Apoi face la fel cu fiecare parte.
- Ω(n log n)
- Θ(n log n)
- O(n²)
- O(log n)
- nu
- 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
- pivot
- pe poziția finală
Încearcă: Alege o listă inversată. Pivotul e mereu cea mai mică sau cea mai mare valoare rămasă, deci o parte e mereu goală și costul urcă spre n².
Cum funcționează
Aici pivotul e ultima valoare din interval. De la stânga la dreapta, fiecare valoare care nu e mai mare decât pivotul e mutată prin schimbare în partea stângă. Apoi pivotul ajunge între cele două părți, unde rămâne definitiv. Fiecare parte e sortată apoi la fel.
Când este o alegere bună
Unul dintre cele mai rapide moduri de sortare în practică, și aproape nu folosește memorie suplimentară. Dar dacă alege mereu un pivot prost, de exemplu pe o listă deja sortată, devine lent. Versiunile reale aleg pivotul cu mai multă grijă.