Sortarea rapidă
Sortarea rapidă (quicksort) este unul dintre cei mai folosiți algoritmi de sortare. Alege un pivot, împarte lista în valorile mai mici decât pivotul și restul, apoi sortează la fel cele două părți. E rapidă în practică și nu are nevoie de o listă suplimentară, dar cât de rapidă depinde de pivot.
Ideea
Alegeți o valoare drept pivot. Rearanjați lista astfel încât fiecare valoare mai mică decât pivotul să fie înaintea lui și fiecare altă valoare după el. Această rearanjare se numește partiționare și lasă pivotul exact unde îi este locul în lista sortată. Cele două părți sunt acum probleme independente: sortați-le pe fiecare cu sortarea rapidă. O parte cu o singură valoare sau fără nicio valoare e deja sortată.
Partiționarea, pas cu pas
Aplicația folosește partiționarea Lomuto. Pivotul e mutat la capătul părții. Un marcaj pornește de la început: tot ce e înaintea lui e mai mic decât pivotul. Fiecare altă valoare e comparată cu pivotul; dacă e mai mică, e interschimbată pe poziția marcajului, iar marcajul avansează o poziție. La final, pivotul e interschimbat pe poziția marcajului. Luați 5, 1, 4, 2, 8 cu ultima valoare ca pivot: toate cele patru valori sunt mai mici decât 8, deci 8 rămâne la capăt. Partea 5, 1, 4, 2 e partiționată în jurul lui 2, rezultând 1, 2, 4, 5, iar 4, 5 în jurul lui 5. Asta înseamnă 8 comparații, 2 interschimbări și 3 partiționări.
Pivoți buni și pivoți proști
Dacă fiecare pivot ar ajunge la mijloc, fiecare partiționare ar înjumătăți problema, iar sortarea ar necesita circa n log₂ n comparații. Pe o listă aleatorie, pivoții sunt rar perfecți, dar de obicei destul de buni: pentru 40 de valori aleatorii, aplicația numără circa 190 de comparații. Cazul cel mai rău apare când pivotul e mereu cea mai mică sau cea mai mare valoare. Cu ultima valoare ca pivot, exact asta se întâmplă pe o listă deja sortată sau inversată: fiecare partiționare scoate doar pivotul, iar sortarea necesită n(n − 1)/2 comparații, 780 pentru 40 de valori.
Alegerea pivotului
Un pivot aleatoriu face cazul cel mai rău extrem de improbabil pentru orice date de intrare, pentru că nicio ordine anume nu îl poate păcăli. Mediana din trei, adică valoarea mediană dintre primul element, cel din mijloc și ultimul, e ieftină și se descurcă bine cu listele sortate și inversate. Încercați-le pe amândouă pe o listă sortată în aplicație, iar comparațiile scad de la 780 la circa 150. Multe valori egale sunt o altă problemă: ajung toate de aceeași parte a pivotului. O partiționare în trei, care ține valorile egale cu pivotul într-o parte din mijloc, rezolvă asta.
Istorie și utilizare
Tony Hoare a inventat sortarea rapidă în 1959 și a publicat-o în 1961. Partiționarea lui proprie parcurge lista de la ambele capete și face mai puține interschimbări; versiunea Lomuto, mai simplă, prezentată aici, a devenit populară prin manuale. Sortarea rapidă sortează pe loc, iar bucla ei interioară e foarte scurtă, așa că în practică e de obicei mai rapidă decât sortarea prin interclasare, deși nu e stabilă. Introsort, sortarea din biblioteca standard C++, rulează sortarea rapidă și trece la heapsort dacă partiționările devin prea inegale, așa că cazul cel mai rău rămâne n log n.
Explorați
Deschideți aplicația și apăsați Pas. Partea care se partiționează e umbrită, pivotul are culoarea lui, iar linia întreruptă marchează capătul părții stângi, adică al valorilor mai mici decât pivotul. Fiecare pivot devine verde când ajunge pe locul final. Alegeți o listă sortată și ultima valoare ca pivot, apoi treceți la mediana din trei și comparați contoarele.
Întrebări frecvente
Care este complexitatea în timp a sortării rapide?
O(n log n) în medie și cu pivoți buni, O(n²) în cazul cel mai rău. Sortează pe loc; recursivitatea are nevoie de O(log n) memorie suplimentară când partea mai mică e sortată prima.
Care este diferența dintre partiționarea Lomuto și cea Hoare?
Lomuto folosește un singur marcaj și parcurge lista de la stânga la dreapta, ceea ce e ușor de urmărit și e ce arată această aplicație. Hoare parcurge lista de la ambele capete unul spre celălalt și interschimbă perechile aflate de partea greșită, ceea ce face în medie de circa trei ori mai puține interschimbări.
De ce e lentă sortarea rapidă când multe valori sunt egale?
Valorile egale cu pivotul ajung toate de aceeași parte, așa că o listă cu puține valori distincte se împarte inegal, iar o listă de valori egale e la fel de rea ca în cazul cel mai rău. O partiționare în trei, care adună valorile egale cu pivotul la mijloc, evită asta.
Este sortarea rapidă stabilă?
Nu. Interschimbările din timpul unei partiționări mută valori la distanțe mari, așa că valorile egale își pot schimba ordinea.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Încercați sortarea rapidă