Sortarea rapidă ca metodă de programare

În 1960, K. A. Hoare a dezvoltat o metodă de sortare rapidă a informațiilor, care a devenit cea mai faimoasă. Astăzi este utilizat pe scară largă în programare, deoarece are o mulțime de proprietăți pozitive: poate fi folosit pentru cazuri generale, necesită o creștere mică în memorie suplimentară, este compatibil cu diferite tipuri de liste și este convenabil pentru implementare. Există, de asemenea, dezavantajele că sortarea rapidă are: atunci când este utilizată la locul de muncă, multe erori sunt permise și sunt oarecum instabile.

Totuși, aceasta este cea mai studiată versiune. După apariția primelor calcule ale lui Hoar, mulți s-au angajat în studiul său dens. A fost creată o bază largă în ceea ce privește întrebările teoretice privind constatarea timpului petrecut pentru muncă, care a fost susținut de date empirice. Au existat propuneri reale pentru îmbunătățirea algoritmului principal și creșterea vitezei de lucru.

Sortarea rapidă este foarte frecventă, poate fi găsită peste tot. Se bazează pe metoda TList.Sort, care există în toate versiunile (cu excepția lui 1) ale Delphi, funcția de bibliotecă a timpului petrecut în execuție, qsort în C ++.

Principiul de bază al muncii poate fi formulat ca "împărțirea și cucerirea". Există o defalcare a listei în două grupe și sortarea este efectuată pentru fiecare parte singură. Rezultă că trebuie acordată mai multă atenție procesului de separare, în timpul căruia au loc următoarele: elementul de bază este determinat și întreaga listă este deja deplasată față de ea. Un grup de candidați este format la stânga, ale căror valori sunt mai mici, toate celelalte fiind transferate spre dreapta. Se pare că elementul principal din lista sortată este localizat la locul potrivit. Următorul pas este să apelați funcția de sortare recursivă pentru ambele părți ale elementelor față de bază. Procesul de lucru se termină numai atunci când lista conține un singur element, adică va fi sortat. Astfel, în scopul de a stăpâni o funcție de programare ca un fel rapid, este necesar să se cunoască activitatea de algoritmi de nivel inferior: a) selectarea unei baze elementa- b) permutarea cea mai eficientă a listei pentru două seturi, cu valori mai mici și mai mari.

Vom cunoaște principiile primului. Atunci când alegeți un element de bază, în mod ideal, cel din mijloc trebuie selectat din listă. Apoi, atunci când este rupt, este împărțit în două jumătăți egale. Numai calcula valoare medie în listă este foarte dificilă, deci și cea mai rapidă sortare ocolește acest calcul alături. Dar alegerea elementului principal cu valoarea maximă sau minimă nu este, de asemenea, cea mai bună opțiune. În cazul unei astfel de definiții, una dintre listele create va fi garantată ca fiind goală, iar cea de-a doua este depășită. Prin urmare, concluzia că, ca element de bază, trebuie să alegem una mai apropiată de media, dar mai departe de maxim și minim.

Odată ce ați decis asupra alegerii, puteți trece la funcționarea algoritmului de partiționare. Acestea sunt așa-numitele cicluri interne de sortare rapidă. Totul este construit pe două indicatoare rapide: prima va trece prin elemente de la stânga la dreapta, a doua, dimpotrivă, de la dreapta la stânga. Se începe operația de execuție din dreapta: indexul trece prin listă și compară toate valorile cu cea principală. Un ciclu este considerat completat dacă există un element mai mic sau egal cu cel de bază. Adică, valoarea indexului este comparată și scade. În partea stângă, lucrarea este terminată când se găsește o valoare mai mare sau egală. Și aici crește valoarea comparației.

În această etapă a algoritmului de partiționare, care conține un fel rapid, pot apărea două situații. Primul este că indicele din stânga va fi mai mic decât cel din dreapta. Aceasta indică o eroare, adică elementele la care a fost specificat sunt în ordine greșită în listă. Ieșirea este schimbarea locurilor. A doua situație este atunci când ambele coloane sunt egale sau intersectate. Aceasta indică o diviziune reușită a listei, adică lucrarea poate fi considerată completă.