Dacă programați și codul dvs. depășește scrierea unui calculator, veți întâlni de mai multe ori sau ați întâmpinat nevoia de a sorta cutare sau cutare matrice de date. Există multe moduri de sortare. În acest articol le vom analiza pe cele principale și ne vom concentra pe sortarea rapidă.

Conceptul de sortare rapidă

Sortare rapidă - Sortare rapidă sau sortare rapidă. Numele arată clar ce este și de ce. Dar dacă nu este clar, acesta este un algoritm pentru sortarea rapidă a unui tablou, algoritmul are o eficiență de O(n log n) în medie. Ce înseamnă? Aceasta înseamnă că timpul mediu de rulare al algoritmului crește pe aceeași traiectorie ca și graficul acestei funcții. În unele limbi populare Există biblioteci încorporate cu acest algoritm, iar acest lucru sugerează deja că este extrem de eficient. Acestea sunt limbaje precum Java, C++, C#.

Algoritm

Metoda de sortare rapidă folosește recursiunea și strategia de împărțire și cucerire.

1. Un anumit element de referință este căutat în matrice pentru simplitate este mai bine să îl luați pe cel central, dar dacă doriți să lucrați la optimizare, va trebui să încercați diferite opțiuni.

2. În stânga suportului, căutăm un element mai mare decât suportul, în dreapta - mai mic decât suportul, apoi le schimbăm. Facem asta până când maximul din dreapta este mai mic decât minimul din stânga. Astfel, aruncăm toate elementele mici la început, iar pe cele mari la final.

3. Aplicăm recursiv acest algoritm în părțile din stânga și din dreapta ale algoritmului nostru separat, apoi din nou și din nou, până când ajungem la un element sau la un anumit număr de elemente. Care este acest număr de elemente? Există o altă modalitate de a optimiza acest algoritm. Când piesa sortată devine aproximativ egală cu 8 sau 16, atunci poate fi procesată prin sortare convențională, de exemplu sortarea cu bule. În acest fel vom crește eficiența algoritmului nostru, deoarece Nu procesează matrice mici atât de repede pe cât ne-am dori.

În acest fel, întreaga matrice va fi procesată și sortată. Acum să studiem clar acest algoritm

Eficacitatea sortării rapide

Este cel mai rapid sortare algoritm rapid triere? Cu siguranta nu. Acum apar din ce în ce mai multe sortări, momentan cea mai rapidă sortare este Timsort, funcționează extrem de rapid pentru matrice care inițial au fost sortate diferit. Dar nu uitați că metoda de sortare rapidă este una dintre cele mai ușor de scris, aceasta este foarte importantă, deoarece, de regulă, pentru un proiect obișnuit aveți nevoie doar de o scriere simplă, și nu de un algoritm uriaș pe care nu îl puteți scrie; te. Timsort nu este, de asemenea, cel mai complex algoritm, dar cu siguranță nu va primi titlul de cel mai simplu.

Implementarea algoritmului

Ei bine, am ajuns la partea „delicioasă”. Acum să vedem cum este implementat acest algoritm. După cum am menționat mai devreme, nu este prea dificil de implementat, este chiar simplu. Dar vom analiza în continuare pe deplin fiecare acțiune a codului nostru, astfel încât să înțelegeți cum funcționează sortarea rapidă.

Metoda noastră se numește quickSort. Rulează algoritmul principal, în care trecem tabloul, primul și ultimul său element. Stocăm primul și ultimul element al segmentului sortat în variabile i și k pentru a nu modifica aceste variabile, deoarece avem nevoie de ele. Apoi verificăm distanța dintre primul și ultimul verificat: este mai mare sau egală cu unu? Dacă nu, atunci am ajuns în centru și trebuie să ieșim din sortarea acestui segment, iar dacă da, atunci continuăm sortarea.

Apoi luăm primul element din segmentul sortat ca element suport. Facem următorul ciclu până ajungem în centru. În ea mai facem două cicluri: primul - pentru partea stângă și al doilea - pentru dreapta. Le executam atata timp cat sunt elemente care indeplinesc conditia, sau pana ajungem la elementul de sustinere. Apoi, dacă elementul minim este încă în dreapta, iar elementul maxim este în stânga, le schimbăm. Când ciclul se termină, schimbăm primul element și elementul de referință, dacă elementul de referință este mai mic. Apoi facem recursiv algoritmul nostru pentru secțiunile din dreapta și din stânga ale matricei și continuăm până când ajungem la o secțiune de 1 element. Apoi toți algoritmii noștri recursivi vor reveni și vom ieși complet din sortare. De asemenea, în partea de jos există o metodă de swap - o metodă complet standard pentru sortarea unei matrice prin înlocuire. Pentru a nu scrie elemente de înlocuire de mai multe ori, scriem o dată și schimbăm elementele din această matrice.

În concluzie, putem spune că în ceea ce privește raportul calitate-complexitate, sortarea rapidă se află pe poziția de lider printre toți algoritmii, așa că cu siguranță ar trebui să țineți cont de metodă și să o utilizați dacă este necesar în proiectele dvs.

Până acum, singura publicație despre sortare pe blogul meu a fost. Este timpul să o reparăm! Nu voi face planuri grandioase pentru a cuceri toate tipurile de sortare, dar voi începe cu una dintre cele mai populare - sortarea rapidă.

Nu voi fi primul și nu voi fi ultimul care spune că „rapid” este doar în nume și acum există o mulțime de analogi și, în general, fiecare tip de date necesită o sortare proprie. Da, totul este adevărat, dar acest adevăr nu se schimbă simplu fapt, Ce propria ta implementare a sortării rapide îți acutizează abilitățile de programare în general , și va fi mereu în cursurile universitare, sunt sigur de asta. Din aceleași motive, a fost ales limbajul de programare pentru implementare, deoarece puteți exersa imediat folosirea pointerilor în C/C++.

Îmi propun să trecem la treabă și mai întâi să luăm în considerare pe scurt esența algoritmului.

Cât de rapidă funcționează

Diagrama algoritmului poate fi descrisă după cum urmează:

1. Alege de sprijin element într-o matrice - se găsește adesea o variantă cu un element central.
2. Împărțiți matricea în două părți astfel: toate elementele din stânga piese care mai mare sau egal sprijin, arunca în corect , în mod similar, toate elementele din corect , care mai mic sau egal îl aruncăm la suport stânga Parte.
3. Ca urmare a pasului anterior, elementele care sunt mai mici sau egale cu cea centrală vor rămâne în partea stângă a matricei, iar elementele care sunt mai mari sau egale cu dreapta vor rămâne.
   Acest lucru poate fi arătat clar astfel:
   |———————|—————————|———————|
   | mas[i]<= mid | mid = mas | mas[i] >= mijlocul |
   |———————-|—————————|———————|
4. Repetăm ​​acțiunea recursiv pentru părțile din stânga și din dreapta ale matricei.

Intrările în recursivitate se vor opri în momentul în care dimensiunea ambelor părți este mai mică sau egală cu una.

Am împrumutat o ilustrare a unui pas al algoritmului, este dureros de clar.

Implementarea recursiva a sortării rapide

Funcția ia ca intrare matricea în sine (un pointer către început) și dimensiunea acesteia.

Void qsortRecursive(int *mas, int size) ( //Pointers la începutul și sfârșitul matricei int i = 0; int j = dimensiune - 1; //Element central al tabloului int mid = mas; //Împărțiți array do ( // Trecem prin elemente, căutându-le pe cele care trebuie transferate într-o altă parte // În partea stângă a matricei sărim (lăsăm pe loc) elementele care sunt mai mici decât cea centrală while(mas[ eu]< mid) { i++; } //В правой части пропускаем элементы, которые больше центрального while(mas[j] >mid) ( j--; ) // Schimbați elemente dacă (i<= j) { int tmp = mas[i]; mas[i] = mas[j]; mas[j] = tmp; i++; j--; } } while (i <= j); //Рекурсивные вызовы, если осталось, что сортировать if(j >0) ( //"Piesă din stânga" qsortRecursive(mas, j + 1); ) dacă (i< size) { //"Првый кусок" qsortRecursive(&mas[i], size - i); } }

Concluzie

Această sarcină simultan vă ajută să înțelegeți cum funcționează recursiunea și vă învață cum să urmăriți modificările datelor în timpul execuției algoritmului. Este recomandat să „mergi înainte” și să-l scrii singur, dar tot aici este implementarea mea, s-ar putea să o consider util. Asta e tot pentru mine, multumesc pentru atentie!

O( n) auxiliar
O (log n) auxiliar (Sedgwick 1978)

Sortare rapidă, Hoare sort(sortare rapidă în engleză), numită adesea qsort(după nume în biblioteca standard C) este un algoritm de sortare binecunoscut dezvoltat de informaticianul englez Charles Hoare în timpul lucrului său la Universitatea de Stat din Moscova în 1960.

algoritm sortare rapidă (A, ia, salut) este dacă uite< hi apoi p:= partiție (A, lo, hi) sortare rapidă (A, lo, p – 1) sortare rapidă (A, p + 1, hi) algoritm partiție (A, lo, hi) este pivot:= A i:= lo - 1 pentru j:=lo la salut - 1 do dacă A[j] ≤ pivot apoi i:= i + 1 schimb A[i] cu A[j] schimb A cu A reveni i+1

Sortarea întregii matrice se poate face prin sortare rapidă (A, 1, lungime (A)) .

Hoare despărțitor

Această schemă folosește doi indici (unul la începutul matricei, celălalt la sfârșit), care se apropie unul de celălalt până când există o pereche de elemente în care unul este mai mare decât referința și este situat înaintea acesteia, iar al doilea este mai mic. și se află după el. Aceste elemente sunt schimbate. Schimbul are loc până când indicii se intersectează. Algoritmul returnează ultimul index. . Schema Hoare este mai eficientă decât schema Lomuto, deoarece în medie există de trei ori mai puține schimburi de elemente, iar partiționarea este mai eficientă, chiar și atunci când toate elementele sunt egale. Similar cu schema Lomuto, această schemă arată, de asemenea, eficacitate în O(n 2) când matricea de intrare este deja sortată. Sortarea folosind această schemă este instabilă. Rețineți că poziția finală a elementului de referință nu este neapărat aceeași cu indexul returnat. Pseudocod:

algoritm sortare rapidă (A, ia, salut) este dacă uite< hi apoi p:= partiție (A, lo, hi) sortare rapidă (A, lo, p) sortare rapidă (A, p + 1, hi) algoritm partiție (A, lo, hi) este pivot:= A i:= lo - 1 j:= hi + 1 buclă pentru totdeauna do i:= i + 1 în timp ce A[i]< pivot do j:= j - 1 în timp ce A[j] > pivot dacă i >= j apoi reveni j schimbați A[i] cu A[j]

Elemente care se repetă

Pentru a îmbunătăți performanța când cantitati mari elemente identice în matrice, se poate aplica procedura de împărțire a matricei în trei grupe: elemente mai mici decât cea de referință, egale cu aceasta și mai mari decât aceasta. (Bentley și McIlroy numesc aceasta „partiție grasă.” Această partiție este folosită în funcție qsortîn cea de-a șaptea versiune a Unix. ). Pseudocod:

algoritm sortare rapidă (A, ia, salut) este dacă uite< hi apoi p:= pivot (A, lo, hi) stânga, dreapta:= partiție (A, p, lo, hi) // returnează două valori sortare rapidă (A, jos, stânga) sortare rapidă (A, dreapta, salut)

Evaluarea complexității algoritmului

Este clar că operația de împărțire a unui tablou în două părți în raport cu elementul de referință necesită timp. Deoarece toate operațiunile de partiționare efectuate la aceeași adâncime de recursivitate procesează părți diferite ale matricei originale, a căror dimensiune este constantă, în total la fiecare nivel de recursivitate va fi de asemenea necesar O (n) (\displaystyle O (n)) operațiuni. În consecință, complexitatea generală a algoritmului este determinată doar de numărul de diviziuni, adică de adâncimea recursiunii. Adâncimea recursiunii, la rândul său, depinde de combinația datelor de intrare și de metoda de definire a elementului de referință.

Cel mai bun caz. În versiunea cea mai echilibrată, cu fiecare operațiune de divizare, matricea este împărțită în două părți identice (plus sau minus un element), prin urmare, adâncimea maximă de recursivitate la care dimensiunile subgrupurilor procesate vor ajunge la 1 va fi. Ca rezultat, numărul de comparații făcute prin sortare rapidă ar fi egal cu valoarea expresiei recursive C n = 2 ⋅ C n / 2 + n (\displaystyle C_(n)=2\cdot C_(n/2)+n), care oferă complexitatea generală a algoritmului O (n ⋅ log 2 ⁡ n) (\displaystyle O(n\cdot \log _(2)n)). Medie. Complexitatea medie cu o distribuție aleatorie a datelor de intrare poate fi estimată doar probabilistic.În primul rând, este necesar să rețineți că, în realitate, nu este necesar ca elementul pivot să împartă matricea în două de fiecare dată. identic piese. De exemplu, dacă în fiecare etapă există o împărțire în matrice cu lungimea de 75% și 25% din original, adâncimea recursiunii va fi egală cu , iar acest lucru dă în continuare complexitate. În general, pentru orice fix relaţia dintre stânga şi laturile drepte separare, complexitatea algoritmului va fi aceeași, doar cu constante diferite. Vom considera o diviziune „reușită” ca fiind una în care elementul de susținere se află printre cele 50% centrale din elementele părții divizate a matricei; În mod clar, probabilitatea de noroc cu o distribuție aleatorie a elementelor este de 0,5. În cazul în care divizarea are succes, dimensiunile subajelor alocate nu vor fi mai mici de 25% și nu mai mult de 75% din original. Deoarece fiecare subbary alocat va avea, de asemenea distribuție aleatorie , toate aceste argumente se aplică oricărei etape de sortare și oricărui fragment inițial al matricei. O diviziune reușită oferă o adâncime de recursivitate de cel mult log 4 / 3 ⁡ n (\displaystyle \log _(4/3)n). Deoarece probabilitatea de noroc este 0,5, pentru a obține k (\displaystyle k) vor fi necesare în medie diviziuni de succes 2 ⋅ k (\displaystyle 2\cdot k) apeluri recursive la elementul de referință k s-a trezit cândva printre cei 50% centrali ai matricei. Aplicând aceste considerații, putem concluziona că în medie adâncimea recursiunii nu va depăși O (n) (\displaystyle O (n)) 2 ⋅ log 4 / 3 ⁡ n (\displaystyle 2\cdot \log _(4/3)n) , care este egal. Cel mai rău caz.În versiunea cea mai dezechilibrată, fiecare diviziune produce două sub-mare de dimensiuni 1 și , adică cu fiecare apel recursiv, matricea mai mare va fi cu 1 mai scurtă decât timpul precedent. Acest lucru se poate întâmpla dacă fie cel mai mic, fie cel mai mare element dintre toate procesate este selectat ca element de referință în fiecare etapă. Cu cea mai simplă alegere a unui element de referință - primul sau ultimul din matrice - un astfel de efect va fi dat de o matrice deja sortată (în ordine înainte sau inversă) pentru mijlocul sau orice alt element fix, „matricea în cel mai rău caz; ” poate fi, de asemenea, special selectat. În acest caz veți avea nevoie n - 1 (\displaystyle n-1) operațiunile de separare, iar timpul total de funcționare va fi

∑ i = 0 n (n - i) = O (n 2) (\displaystyle \textstyle \sum _(i=0)^(n)(n-i)=O(n^(2)))

operatii, adica sortarea se va efectua in timp patratic. Dar numărul de schimburi și, în consecință, timpul de funcționare nu este cel mai mare dezavantaj al său. Mai rău este că, în acest caz, adâncimea recursiunii la executarea algoritmului va ajunge la n, ceea ce va însemna salvarea adresei de retur și a variabilelor locale ale procedurii de divizare a matricei de n ori. Pentru valori mari ale lui n, cel mai rău caz ar putea duce la epuizarea memoriei (depășirea stivei) în timp ce programul rulează.

Avantaje și dezavantaje

Avantaje:

Defecte: ÎmbunătățiriÎmbunătățirile algoritmului vizează în principal eliminarea sau atenuarea deficiențelor menționate mai sus, drept urmare toate acestea pot fi împărțite în trei grupe: realizarea algoritmului robust, eliminarea degradării performanței prin alegerea specială a elementului de referință și protejarea împotriva depășirii stivei de apeluri din cauza

• adâncime mare

• recursivitate atunci când datele de intrare eșuează. Problema de instabilitate este rezolvată prin extinderea cheii cu indexul original al elementului din matrice. În cazul egalității cheilor principale, comparația se face prin index, excluzând astfel posibilitatea modificării poziției relative a elementelor egale. Această modificare nu este gratuită - necesită memorie suplimentară O(n) și o trecere completă prin matrice pentru a păstra indicii originali. Degradarea vitezei în cazul unui set nereușit de date de intrare se rezolvă în două direcții diferite: reducerea probabilității ca cel mai rău caz să apară printr-o alegere specială a elementului suport și utilizarea diferitelor tehnici tehnice care asigură

• Selectarea elementului din mijloc. Elimină degradarea datelor presortate, dar lasă posibilitatea apariției accidentale sau a selecției intenționate a unei matrice „proaste”.
• Selectarea medianei a trei elemente: primul, mijlocul și ultimul. Reduce probabilitatea apariției unui caz cel mai rău în comparație cu selectarea elementului din mijloc.
• Selectare aleatorie. Probabilitatea ca cel mai rău caz să apară întâmplător devine extrem de mică, iar selecția deliberată devine practic imposibilă. Timpul de execuție așteptat al algoritmului de sortare este O( n lg n).

Dezavantajul tuturor metodelor complicate de selectare a unui element de sprijin este supraîncărcarea suplimentară; cu toate acestea, ele nu sunt atât de grozave.

• Pentru a evita eșecul programului din cauza adâncimii mari de recursivitate, pot fi utilizate următoarele metode:

	Există un Wikibook pe acest subiect „Exemple de implementare a sortării rapide”

Pseudocod.
quickSort(matrice a, limita superioară N) ( Selectați elementul pivot p - mijlocul matricei Împărțiți matricea la acel element Dacă sub-taxa din stânga lui p conține mai mult de un element, apelați quickSort pe el. Dacă sub-taxa din dreapta lui p conține mai mult de un element, apelați lui quickSort ) Implementare în C.
șablon void quickSortR(T* a, long N) ( // Intrarea este un tablou a, a[N] este ultimul său element. lung i = 0, j = N-1; // pune pointeri către locurile originale T temp, p; p = a[ N>>1]; // element central// procedura de divizare< p) i++; while (a[j] >face (în timp ce (a[i]<= j) { temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j--; } } while (i<=j); p)j--; dacă (i

// apeluri recursive, dacă există ceva de sortat

dacă (j > 0) quickSortR(a, j);

dacă (N > i) quickSortR(a+i, N-i); )

Sortarea folosește memorie suplimentară deoarece adâncimea aproximativă a recursiunii este O(log n) și subapelurile recursive sunt împinse în stivă de fiecare dată.

Modificări de cod și metodă

Din cauza recursiunii și a altor sarcini, Quicksort poate să nu fie atât de rapid pentru matrice scurte. Prin urmare, dacă există mai puține elemente CUTOFF în matrice (constantă dependentă de implementare, de obicei între 3 și 40), se apelează sortarea prin inserție. Creșterea vitezei poate fi de până la 15%.

Pentru a implementa metoda, puteți modifica funcția quickSortR înlocuind ultimele 2 linii cu

Dacă (j > CUTOFF) quickSortR(a, j);

if (N > i + CUTOFF) quickSortR(a+i, N-i);<=CUTOFF элементов, отсортированные друг относительно друга. Близкие элементы имеют близкие позиции, поэтому, аналогично сортировке Шелла, вызывается insertSort(), которая доводит процесс до конца.

Astfel, matricele de elemente CUTOFF și mai puține nu vor fi sortate, iar la sfârșitul quickSortR() tabloul va fi împărțit în părți succesive din Șablon void qsortR(T *a, dimensiune lungă) ( quickSortR(a, dimensiune-1); insertSort(a, dimensiune);}

1. // insertSortGuarded este mai rapid, dar are nevoie de funcția setmax().
2. În cazul recursiunii explicite, la fel ca în programul de mai sus, nu numai limitele subbary-urilor sunt stocate pe stivă, ci și o serie de parametri complet inutile, cum ar fi variabilele locale. Dacă emulați o stivă în mod programatic, dimensiunea acestuia poate fi redusă de mai multe ori.
3. Cu cât matricea este împărțită în părți mai egale, cu atât mai bine. Prin urmare, este recomandabil să luați media a trei ca referință, iar dacă matricea este suficient de mare, atunci a nouă elemente arbitrare.
4. Lasă secvențele de intrare să fie foarte proaste pentru algoritm. De exemplu, sunt selectați special, astfel încât elementul din mijloc să se dovedească a fi minim de fiecare dată. Cum să faceți QuickSort rezistent la astfel de „sabotaj”? Este foarte simplu să alegeți un element aleatoriu al matricei de intrare ca referință. Apoi, orice tipare neplăcute din fluxul de intrare va fi neutralizat. O altă opțiune este să rearanjați aleatoriu elementele matricei înainte de sortare.

Să luăm în considerare cel mai rău caz, când elementele de sprijin selectate aleatoriu s-au dovedit a fi foarte proaste (aproape de extreme). Probabilitatea acestui lucru este extrem de mică, deja la n = 1024 este mai mică de 2 -50, deci interesul este mai mult teoretic decât practic. Cu toate acestea, comportamentul de „sortare rapidă” este „punctul de referință” pentru algoritmii de divide-and-conquer implementați în mod similar. Nu peste tot este posibil să se reducă probabilitatea celui mai rău caz la aproape zero, așa că această situație merită studiată.

Lăsați, pentru certitudine, să selectați cel mai mic element un min de fiecare dată. Apoi procedura de divizare va muta acest element la începutul matricei și două părți vor fi trimise la următorul nivel de recursivitate: una din singurul element a min , cealaltă conținând n-1 elemente rămase ale matricei. Apoi procesul se va repeta pentru o porțiune de (n-1) elemente.. Și așa mai departe..
Folosind cod recursiv ca cel de mai sus, aceasta ar însemna n apeluri recursive imbricate la quickSort.
Fiecare apel recursiv înseamnă stocarea de informații despre starea actuală a lucrurilor. Astfel, sortarea necesită O(n) memorie suplimentară... Și nu oriunde, ci pe stivă. Dacă n este suficient de mare, o astfel de cerință poate duce la consecințe imprevizibile.

Pentru a elimina această situație, puteți înlocui recursiunea cu iterație prin implementarea unei stive bazate pe matrice. Procedura de divizare va fi efectuată ca o buclă.
De fiecare dată când matricea este împărțită în două părți, o solicitare va fi trimisă stivei pentru a o sorta pe cea mai mare, iar cea mai mică va fi procesată în următoarea iterație. Interogările vor fi scoase din stivă pe măsură ce procedura de partiționare devine liberă de sarcinile curente. Sortarea se termină când nu mai sunt cereri.

Pseudocod.
QuickSort iterativ (matrice a, dimensiune mărime) (Aplicați o solicitare de sortare a matricei de la 0 la dimensiunea-1 pe stivă. face (Opți limitele lb și ub ale matricei curente din stivă. face ( 1. Efectuați o împărțire) operațiune pe matricea curentă a. 2. Trimiteți limitele celei mai mari părți rezultate în stivă 3. Mutați limitele ub, lb astfel încât să indice partea mai mică), în timp ce partea mai mică este formată din două sau mai multe. elemente) în timp ce există cereri pe stivă) Implementare în C.
#define MAXSTACK 2048 // dimensiunea maximă a stiveișablon void qSortI(T a, long size) ( long i, j; // indicii implicați în împărțire lung lb, ub; // limitele fragmentului sunt sortate în buclă lung lbstack, ubstack; // stivă de solicitări // fiecare cerere este specificată de o pereche de valori, // și anume: stânga (lbstack) și dreapta (ubstack) // limitele intervalului stackpos lung = 1; // poziţia curentă a stivei ppos lungi; // mijlocul matricei pivot T; // element suport T temp; lbstack = 0; ubstack = dimensiunea-1; face (// Luați limitele lb și ub ale matricei curente din stivă.< pivot) i++; while (pivot < a[j]) j--; if (i <= j) { temp = a[i]; a[i] = a[j]; a[j] = temp; i++; j--; } } while (i <= j); lb = lbstack[ stackpos ]; ub = ubstack[ stackpos ]; stackpos--; face (// Pasul 1. Împărțit prin element pivot< ppos) { ppos = (lb + ub) >> 1;// Pasul 1. Împărțit prin element pivot< ub) { i = lb; j = ub; pivot = a; face (în timp ce (a[i] // Acum indicatorul i indică începutul sub-taxului drept,// j - la capătul din stânga (vezi ilustrația de mai sus), lb ? j? eu? ub. // Este posibil ca pointerul i sau j să depășească limita matricei // Pașii 2, 3. Împingeți cea mai mare parte pe stivă și mutați lb,ub dacă (i // partea dreaptă este mai mare// dacă conține mai mult de 1 element, este necesar< ub); stackpos++;// sortare, cerere de stivuire lbstack[ stackpos ] = i;}

ubstack[ stackpos ] = ub;

) ub = j;

// următoarea iterație a împărțirii // va funcționa cu partea stângă) altfel (

Algoritm

1. // partea stângă este mai mare
2. dacă (j > lb) ( stackpos++; lbstack[ stackpos ] = lb; ubstack[ stackpos ] = j; ) lb = i;
   • ) ) în timp ce (lb
   • // în timp ce partea mai mică conține mai mult de 1 element
   • ) în timp ce (stackpos != 0);
   • // în timp ce există cereri pe stivă
   • Dimensiunea stivei cu această implementare este întotdeauna de ordinul O(log n), astfel încât valoarea specificată în MAXSTACK este mai mult decât suficientă.
3. Salutare tuturor! Voi vorbi despre algoritmul de sortare rapidă și voi arăta cum poate fi implementat programatic.

Deci, sortarea rapidă sau, după numele funcției din C, Qsort, este un algoritm de sortare a cărui complexitate

în medie
{
este O(n log(n)). Esența sa este extrem de simplă: este selectat un așa-zis element de referință, iar matricea este împărțită în 3 subbariere: mai mică decât referința, egală cu referința și mai mare decât referința. Acest algoritm este apoi aplicat recursiv sub-tarilor.
Selectarea elementului suport Împărțim matricea în 3 părți
Creăm variabilele l și r - indicii, respectiv, ai începutului și sfârșitului subbarajului luat în considerare<= r)
{
Creșteți l până când al l-lea element este mai mic decât cel de referință< piv)
Descreșteți r până când elementul r este mai mare decât cel de referință
Dacă l este tot mai mic decât r, atunci schimbați elementele l-a și r-a, creșteți l și decrementați r
Dacă l devine brusc mai mare decât r, atunci întrerupem ciclul
Repetăm ​​recursiv până ajungem la o matrice de 1 element<= r)
Ei bine, nu pare atât de dificil. O putem implementa în C? Nici o problemă!
}
dacă (b< r)
qsort(b,r);
dacă (e > l)
qsort(l, e);
} /* ----- sfârșitul funcției qsort ----- */

// qsort (0, n-1);

* Acest cod sursă a fost evidențiat cu Sursa de evidențiere a codului .

Această implementare are o serie de dezavantaje, cum ar fi posibila depășire a stivei din cauza cantității mari de recursivitate imbricată și a faptului că elementul de referință este întotdeauna considerat cel din mijloc. De exemplu, acest lucru poate fi normal, dar atunci când rezolvă, de exemplu, probleme la olimpiade, un juriu viclean poate selecta special astfel de teste, astfel încât această soluție să le funcționeze prea mult timp și să nu depășească limita. În principiu, puteți lua ca element de referință orice element, dar este mai bine ca acesta să fie cât mai aproape de mediană, astfel încât să îl puteți alege la întâmplare sau să luați valoarea medie de la prima, medie și ultima. Dependența performanței de elementul de referință este unul dintre dezavantajele algoritmului; Dacă mai aveți nevoie de o sortare care este garantată să funcționeze rapid, puteți utiliza, de exemplu, heapsort, care funcționează întotdeauna strict în O(n log n). De obicei, Qsort încă depășește alte tipuri, nu necesită multă memorie suplimentară și este destul de simplu de implementat, așa că se bucură de o popularitate binemeritată.

L-am scris eu, aruncând ocazional o privire la Wikipedia. Profitând de această ocazie, aș dori să-mi exprim recunoștința față de minunatii profesori și studenți ai PetrSU, care m-au învățat multe lucruri utile, inclusiv acest algoritm!

Etichete: Qsort, sortare rapidă, algoritmi de sortare, algoritmi, C