.
QuickSort
QuickSort este un pic prea complex pentru a fi ușor de imaginat cu oamenii, așa că haideți să ne apropiem puțin de cod. Pentru început, să ne imaginăm că aveți o listă neordonată, sau un array, de opt numere pe care doriți să le ordonați.
4 2 13 6 15 12 7 9
Ați putea folosi MergeSort, dar ați auzit că QuickSort este în general mai rapid, așa că vă decideți să îl încercați. Primul dvs. pas este să alegeți un număr din listă numit pivot. Alegerea numărului pivot corect va face diferența în ceea ce privește rapiditatea cu care QuickSort-ul dvs. funcționează și există formule gata făcute care pot fi urmate pentru alegerea unor pivoți buni. Dar, deocamdată, haideți să păstrăm lucrurile simple și să alegem ultimul număr din matrice pentru numărul nostru pivot: 9.
4 2 13 6 15 12 7 9
Pentru a face următorul pas mai ușor de urmărit, vom crea un separator la începutul matricei și îl vom reprezenta cu semnul de lire sterline.
# 4 2 13 6 15 12 7 9
Mutându-ne de la stânga la dreapta prin tabloul nostru, obiectivul nostru este să punem orice număr mai mic decât pivotul (9) la stânga separatorului și orice număr mai mare (sau egal cu) pivotul la dreapta separatorului. Începem cu primul număr din matricea noastră: 4. Pentru a-l muta în stânga separatorului, pur și simplu mutăm separatorul în sus cu un element:
4 # 2 13 6 15 12 7 9
Facem același lucru cu următorul număr: 2.
4 2 # 13 6 15 12 7 9
Dar apoi ajungem la 13, care este mai mare decât numărul pivot 9 și se află deja în partea dreaptă a separatorului. Așa că îl lăsăm în pace. Apoi ajungem la 6, care trebuie să meargă în stânga separatorului. Așa că, mai întâi, îl interschimbăm cu 13 pentru a-l pune în poziție:
4 2 # 6 13 15 12 7 9
Apoi mutăm separatorul pe lângă el:
4 2 6 # 13 15 12 7 9
Următorul este 15, care este deja la dreapta separatorului, așa că îl lăsăm în pace. Apoi avem 12. Același lucru. Dar 7, ultimul nostru număr înainte de a ajunge la pivot, are nevoie de același tip de ajutor în deplasare ca și 6. Așa că îl schimbăm pe 7 cu 13 pentru a-l aduce în poziție:
4 2 6 # 7 15 12 13 9
Apoi, încă o dată, mutăm separatorul pe lângă el:
4 2 6 7 # 15 12 13 9
În cele din urmă, ajungem la numărul nostru pivot: 9. Urmând aceeași logică de mai sus, schimbăm 15 cu 9 pentru a obține numărul pivot acolo unde trebuie să fie:
4 2 6 7 # 9 12 13 15
Din moment ce toate numerele din stânga lui 9 sunt acum mai mici decât 9, iar toate numerele din dreapta lui 9 sunt mai mari decât 9, am terminat cu primul nostru ciclu de QuickSort. În continuare, vom trata fiecare set de patru numere de o parte și de alta a separatorului ca pe o nouă matrice căreia să îi aplicăm QuickSort. Vă vom scuti de detalii, dar următoarea rundă ne va oferi patru perechi de numere pe care să aplicăm cu ușurință ultima rundă de QuickSort. Rezultatul final va fi următoarea listă ordonată, care ne-a luat mai puțin timp să o generăm decât ar fi făcut-o cu mai simplul MergeSort:
2 4 6 7 9 12 13 15
Scheat sheet algoritmi de sortare
Aceștia sunt cei mai comuni algoritmi de sortare, cu câteva recomandări pentru când să îi folosim. Interiorizați-le! Sunt folosiți peste tot!
Heap sort: Atunci când nu aveți nevoie de o sortare stabilă și vă interesează mai mult performanța în cel mai rău caz decât performanța în cazul mediu. Este garantat a fi O(N log N) și utilizează O(1) spațiu auxiliar, ceea ce înseamnă că nu veți rămâne neașteptat fără spațiu în heap sau stivă la intrări foarte mari.
Introsort: Aceasta este o sortare rapidă care trece la o sortare pe grămadă după o anumită adâncime de recursivitate pentru a ocoli cazul cel mai rău al sortării rapide O(N²). Este aproape întotdeauna mai bună decât o sortare rapidă simplă, deoarece obțineți cazul mediu al unei sortări rapide, cu performanțe garantate O(N log N). Probabil că singurul motiv pentru a utiliza o sortare de tip heap în locul acesteia este în cazul sistemelor cu constrângeri severe de memorie, unde spațiul în stivă O(log N) este practic semnificativ.
Sortare prin inserție: Atunci când N este garantat a fi mic, inclusiv ca și caz de bază al unei sortări rapide sau al unei sortări prin fuziune. Deși este O(N²), are o constantă foarte mică și este o sortare stabilă.
Sortare cu bule, sortare prin selecție: Atunci când faceți ceva rapid și murdar și, din anumite motive, nu puteți folosi pur și simplu algoritmul de sortare al bibliotecii standard. Singurul avantaj pe care acestea îl au față de sortarea prin inserție este că sunt puțin mai ușor de implementat.
Sortare rapidă: Atunci când nu aveți nevoie de o sortare stabilă și performanța în cazul mediu contează mai mult decât performanța în cel mai rău caz. O sortare rapidă este O(N log N) în medie, O(N²) în cel mai rău caz. O implementare bună utilizează O(log N) de stocare auxiliară sub formă de spațiu în stivă pentru recursivitate.
Sortare mixtă: Atunci când aveți nevoie de o sortare stabilă, O(N log N), aceasta este cam singura opțiune. Singurele sale dezavantaje sunt că utilizează un spațiu auxiliar O(N) și are o constantă puțin mai mare decât o sortare rapidă. Există câteva sortări de fuziune in situ, dar, după părerea mea, toate sunt fie instabile, fie mai puțin bune decât O(N log N). Chiar și sortările O(N log N) in place au o constantă mult mai mare decât cea a sortării fuzionate obișnuite, astfel încât sunt mai mult curiozități teoretice decât algoritmi utili.