În 1960 K.A.Hoare a dezvoltat cea mai faimoasă metodă de sortare rapidă a informațiilor. Astăzi este utilizat pe scară largă în programare, deoarece are o mulțime de proprietăți pozitive: poate fi utilizat pentru cazuri generale, necesită o creștere mică a memoriei suplimentare, este compatibil cu diferite tipuri de liste și este convenabil pentru implementare. Dar există, de asemenea, dezavantaje pe care le are Quicksort: atunci când sunt utilizate în muncă, sunt permise multe erori și este oarecum instabil.
Cu toate acestea, aceasta este cea mai studiată versiune.După apariția primelor calcule ale lui Hoare, mulți au început să-l studieze îndeaproape. S-a creat o bază largă pe problemele teoretice de găsire a timpului petrecut la muncă, care au fost susținute de date empirice. Au existat propuneri reale pentru îmbunătățirea algoritmului principal și creșterea vitezei de lucru.
Quicksort este foarte frecvent și poate fiintalneste peste tot. Pe baza acestuia, este implementată metoda TList.Sort, care există în toate versiunile (cu excepția 1) ale Delphi, funcția bibliotecii de timp petrecut în execuție, qsort în C ++.
Principiul de bază al funcționării poate fi formulat ca„împarte și stăpânește”. Lista este împărțită în două grupuri și sortarea se face pentru fiecare parte de la sine. Prin urmare, rezultă că este necesară o atenție sporită procesului de separare, în timpul căruia se întâmplă următoarele: elementul de bază este determinat și întreaga listă este rearanjată în raport cu acesta. În stânga, este construit un grup de candidați, ale căror valori sunt mai mici, în dreapta, toți ceilalți sunt transferați. Se pare că elementul principal din lista sortată se află la locul potrivit. Următorul pas este să apelați o funcție de sortare recursivă pentru ambele părți ale elementelor în raport cu cea de bază. Procesul de lucru se încheie numai atunci când lista conține un singur element, adică va fi sortat. Astfel, pentru a stăpâni o astfel de funcție de programare ca sortare rapidă, trebuie să cunoaștem funcționarea algoritmilor de nivel inferior: a) alegerea elementului de bază; b) cea mai eficientă rearanjare a listei pentru a obține două seturi cu valori din ce în ce mai mici.
Să ne cunoaștem principiile primului.Atunci când alegeți un element de bază, în mod ideal, cel din mijloc ar trebui să fie selectat din listă. Apoi, când este rupt, va fi împărțit în două jumătăți egale. Este foarte dificil să calculați valoarea medie din listă, prin urmare chiar și cel mai rapid sort ocolește acest calcul. Dar alegerea elementului principal cu valoarea maximă sau minimă nu este nici cea mai bună opțiune. În cazul unei astfel de definiții, una dintre listele create va fi garantată că este goală, iar a doua va fi debordată. De aici concluzia că, ca element de bază, ar trebui să o alegem pe cea mai apropiată de medie, dar mai departe de maxim și minim.
După ce ați făcut alegerea, putețimergeți la lucrarea algoritmului de partiționare. Acestea sunt așa-numitele bucle interioare rapide. Totul este construit pe doi indici care funcționează rapid: primul va trece prin elementele de la stânga la dreapta, al doilea, dimpotrivă, de la dreapta la stânga. Operațiunea de execuție începe în dreapta: indexul trece prin listă și compară toate valorile cu cea principală. Ciclul este considerat complet dacă se găsește un element care este mai mic sau egal cu cel de bază. Adică, are loc o comparație și valoarea indicelui scade. În partea stângă, lucrarea se termină atunci când se găsește o valoare mai mare sau egală. Și aici valoarea crește atunci când este comparată.
În acest stadiu al algoritmului de partiționare,care conține rapid, pot apărea două situații. Primul este că indicele din stânga va fi mai mic decât indicele din dreapta. Aceasta indică o eroare, adică elementele arătate în ordine greșită în listă. Ieșirea este schimbarea locurilor lor. A doua situație este atunci când ambele coloane sunt egale sau încrucișate. Aceasta indică o împărțire cu succes a listei, adică lucrarea poate fi considerată completă.
