- Partea care se partiționează
- Pivot
- Comparate
- Interschimbate
- La locul lor
Sortarea rapidă
Sortarea rapidă (quicksort) alege un pivot, mută fiecare valoare mai mică înaintea lui și fiecare altă valoare după el, apoi sortează la fel cele două părți. După fiecare partiționare, pivotul ajunge pe locul final. Stabiliți cum se alege pivotul, redați sortarea la orice viteză sau parcurgeți-o câte o comparație și vedeți de ce un pivot prost pe o listă sortată face sortarea rapidă lentă. Apăsați Redare pentru a urmări sortarea sau Pas și Înapoi pentru a avansa câte o comparație. Trageți glisorul pentru pași ca să săriți oriunde. Casetele numără comparațiile, interschimbările și partiționările. Alegeți câte bare sunt, cum încep sau introduceți propriile numere, precum și cum se alege pivotul. Cu tabla selectată, săgețile avansează câte un pas, bara de spațiu pornește și pune pauză, iar Home și End sar la început și la sfârșit.
Cum funcționează
- Alegeți câte bare sunt și cum încep: aleatoriu, aproape sortate, inversate sau cu puține valori distincte. Sau introduceți propriile numere.
- Apăsați Redare sau folosiți Pas și Înapoi ca să avansați câte o comparație. Trageți glisorul pentru pași ca să săriți oriunde în sortare.
- Alegeți regula pivotului: ultima valoare, valoarea din mijloc, o valoare aleatorie sau mediana din trei. Încercați-le pe toate pe o listă sortată.
Cum funcționează sortarea rapidă
Alegeți o valoare din partea de sortat drept pivot și mutați-o la capăt. Parcurgeți celelalte valori de la stânga la dreapta; fiecare valoare mai mică decât pivotul este mutată prin interschimbare într-o parte stângă care crește de la început. Apoi aduceți pivotul, printr-o interschimbare, imediat după partea stângă. Tot ce e înaintea lui e acum mai mic și nimic de după el nu e, deci pivotul e pe locul final. Sortați la fel partea dinaintea lui și partea de după el, până când fiecare parte e o singură valoare.
De ce contează pivotul
Când pivotul ajunge aproape de mijloc, fiecare partiționare înjumătățește problema, iar comparațiile cresc ca n log n: pentru 40 de valori aleatorii, circa 190. Când pivotul este cea mai mică sau cea mai mare valoare, o parte e goală, iar cealaltă conține tot restul. Cu ultima valoare ca pivot, asta se întâmplă la fiecare pas pe o listă sortată sau inversată, iar sortarea necesită n(n − 1)/2 comparații, 780 pentru 40 de valori. Un pivot aleatoriu sau mediana dintre prima valoare, cea din mijloc și ultima evită asta în practică.
Întrebări frecvente
Cum funcționează sortarea rapidă?
Alege un pivot, partiționează lista astfel încât valorile mai mici să fie înaintea pivotului și restul după el, apoi sortează ambele părți tot cu sortarea rapidă. După fiecare partiționare, pivotul e pe locul final.
De ce e lentă sortarea rapidă pe o listă sortată?
Cu prima sau ultima valoare ca pivot, o listă sortată dă mereu ca pivot cea mai mică sau cea mai mare valoare. O parte a partiționării e atunci goală, deci fiecare partiționare scoate doar o valoare, iar sortarea necesită n(n − 1)/2 comparații. Un pivot aleatoriu sau mediana din trei rezolvă asta în practică.
Este sortarea rapidă mai rapidă decât sortarea prin interclasare?
Adesea, în practică: sortează pe loc, nu are nevoie de buffer, iar bucla interioară e foarte simplă. În medie face ceva mai multe comparații decât sortarea prin interclasare, iar cazul cel mai rău e n², în timp ce sortarea prin interclasare e mereu n log n. Sortările din biblioteci, ca introsort, încep cu sortarea rapidă și trec la heapsort dacă împărțirile devin prea inegale.
Este sortarea rapidă stabilă?
Nu. O partiționare interschimbă valori aflate la distanțe mari, așa că valorile egale își pot schimba ordinea.
Numerele mele sunt trimise undeva?
Nu. Sortarea rulează în browserul dumneavoastră, iar ultimele setări rămân în spațiul de stocare local al acestui browser.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor