Sortare rapida

Sortare rapida
Quicksort rulează pe o listă de numere. Linia albastră este valoarea pivotului .
Clasă	Algoritm de sortare
Structură de date	Variabil
Cel mai rău caz din punct de vedere temporal	$\Theta (n^{2})$ ${\ displaystyle \ Theta (n ^ {2})}$ $\ Theta (n ^ {2})$
Caz optim în timp	$\Theta (n\log _{2}n)$ ${\ displaystyle \ Theta (n \ log _ {2} n)}$ ${\ displaystyle \ Theta (n \ log _ {2} n)}$
Caz mediu în timp	$\Theta (n\log _{2}n)$ ${\ displaystyle \ Theta (n \ log _ {2} n)}$ ${\ displaystyle \ Theta (n \ log _ {2} n)}$ comparații
Cel mai rău caz spațial	Depinde de implementări
Optim	De multe ori
Manual

Sortarerapidă este oinstabilă recursiv în loc algoritmul de sortare . Această procedură recursivă este denumită în mod obișnuit partiție: luând un element numit "pivot" dintr-o structură de date (de exemplu matrice ), elementele minore sunt plasate în stânga în raport cu pivotul și elementele majore din dreapta. Operația este apoi repetată pe cele două seturi rezultate până când structura este complet sortată.

Quicksort, un termen care tradus literal în italiană indică o sortare rapidă, este algoritmul de sortare care are, în cazul mediu, o performanță mai bună decât cele bazate pe comparație. A fost proiectat de Charles Antony Richard Hoare în 1961 .

Istorie

Algoritmul rapid a fost conceput în 1959 de Tony Hoare în timpul unei călătorii în URSS, în timpul unei vizite la Universitatea de Stat din Moscova . La acea vreme, Hoare lucra la un proiect de traducere automată pentru Laboratorul Național de Fizică . În timpul procesului de traducere a devenit necesar să sortați cuvintele rusești înainte de a consulta dicționarul ruso-englez care a fost înregistrat pe bandă magnetică și sortat alfabetic. ^[1] După ce și-a dat seama că utilizarea sortării de inserție ar fi prea lentă, a venit cu o nouă idee de algoritm - Quicksort. El a scris programul cu Autocode referitor la partiție, dar nu a reușit să gestioneze partea referitoare la segmente neordonate. Înapoi în Anglia, i s-a cerut de lucru pentru codificarea unui Shellsort - cel mai eficient algoritm de sortare la acea vreme. Hoare i-a spus șefului său că știe un algoritm mai eficient; șeful a făcut un pariu, de șase bani și a pierdut. Mai târziu, Hoare a aflat despre limbajul ALGOL și capacitatea sa de a gestiona recursivitatea; mulțumită acestuia, el a publicat codul complet în jurnalul principal de informatică al perioadei, Communications of the Association for Computing Machinery ,. ^[2]

Algoritm de bază

Ideea de bază poate fi ușor exprimată în termeni recursivi. În fiecare etapă se efectuează o sortare parțială a unei secvențe de obiecte care urmează a fi sortate. Odată ce un element este luat ca pivot al stadionului, celelalte elemente sunt comparate cu acesta și cele minore sunt plasate în stânga și cele majore în dreapta, indiferent de ordinea lor. După această etapă, știftul se află în poziția sa finală.

Ulterior, sunt organizate noi etape similare în care se efectuează ordonarea parțială a subsecvențelor elementelor care au rămas neordonate, până la epuizarea acestora.

Pseudocodul pentru Quicksort este:

 Proceduri Quicksort (A)
Intrarea A, vectorul a ₁ , a ₂ , a ₃ .. a _n
  începe
    dacă n ≤ 1 atunci returnează A
    altceva
      începe
        alegeți un element pivot la _k
        calculați vectorul A1 din elementele a _i ale lui A astfel încât i ≠ K și a _i ≤ a _k
        calculați vectorul A2 din elementele a _j ale lui A astfel încât j ≠ K și a _j > a _k
        A1 ← Quicksort (A1)
        A2 ← Quicksort (A2)
        returnează A1 · (a _k ) · A2;
      Sfârșit

Specificarea algoritmului

O altă reprezentare grafică a algoritmului Quicksort

Dorim să oferim o versiune mai detaliată a algoritmului care specifică structura datelor utilizate și procesul de partiție. Scopul este de a implementa procedura prin intermediul unei proceduri care calculează secvența ordonată prin schimburi directe între valorile componentelor sale, fără a utiliza vectori suplimentari pentru a menține rezultatele parțiale ale calculului. În acest fel, spațiul de memorie utilizat este redus în esență la celulele necesare pentru a menține vectorul de intrare și pentru a implementa recursivitatea.

Secvența de intrare este reprezentată de vector $A=(A[1],A[2],...A[n])\,\,n\geq 1$ ${\ displaystyle A = (A [1], A [2], ... A [n]) \, \, n \ geq 1}$ $A = (A [1], A [2], ... A [n]) \, \, n \ geq 1$ componente. Pentru orice pereche de numere întregi p, q astfel încât $1\leq p\leq q\leq n$ ${\ displaystyle 1 \ leq p \ leq q \ leq n}$ $1 \ leq p \ leq q \ leq n$ denotăm $A_{p,q}=(A[p],A[p+1],...A[q])$ ${\ displaystyle A_ {p, q} = (A [p], A [p + 1], ... A [q])}$ $A _ {{p, q}} = (A [p], A [p + 1], ... A [q])$ . Nucleul algoritmului este funcția care partiționează setul, pentru comoditate o numim partiție (p, q). Această procedură împarte elementele vectorului $A_{p,q}$ ${\ displaystyle A_ {p, q}}$ $A _ {{p, q}}$ comparativ cu valoarea $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ a primei componente $A[p]$ ${\ displaystyle A [p]}$ $A [p]$ ; această funcție schimbă apoi valoarea componentelor $A_{p,q}$ ${\ displaystyle A_ {p, q}}$ $A _ {{p, q}}$ și returnează un index $l\in [p,p+1,...q]$ ${\ displaystyle l \ in [p, p + 1, ... q]}$ $l \ în [p, p + 1, ... q]$ care se bucură de următoarele proprietăți:

$A[l]$ ${\ displaystyle A [l]}$ $Către]$ își asumă valoarea $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$
$A_{p,l-1}$ ${\ displaystyle A_ {p, l-1}}$ $A _ {{p, l-1}}$ conține valori mai mici sau egale cu $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ conținută inițial în $A_{p+1,q}$ ${\ displaystyle A_ {p + 1, q}}$ $A _ {{p + 1, q}}$
$A_{l+1,q}$ ${\ displaystyle A_ {l + 1, q}}$ ${\ displaystyle A_ {l + 1, q}}$ conține valori mai mari decât $\alpha$ ${\ displaystyle \ alpha}$ $\ alfa$ conținută inițial în $A_{p+1,q}$ ${\ displaystyle A_ {p + 1, q}}$ $A _ {{p + 1, q}}$

Reanalizând algoritmul quicksort descris mai sus, înțelegem că funcția de partiție este punctul de sprijin al operațiilor. În versiunea prezentată aici, elementul pivot este setat la A [p]; acest lucru nu este limitat, deoarece apelantul poate alege un pivot diferit și îl poate plasa în A [p] înainte de a apela funcția. Partiția scanează apoi elementele din stânga, sărind peste cele mai mici ale pivotului și din dreapta, trecând peste cele mai mari; apoi schimbați elementele care opresc scanările și o iau de la capăt. Scanarea începând din stânga se oprește pe elemente mai mari sau egale cu pivotul (și, prin urmare, este blocată de elementul pivot în sine), în timp ce cea care începe din dreapta se oprește când ajunge la un element mai mic decât pivotul (și, prin urmare, este blocat de elementul anterior de la pivot). Pointerii utilizați pentru scanare pot fi, prin urmare, traversați și, atunci când intersecția a avut loc, funcția și-a finalizat activitatea.

În plus față de vectorul A, funcția primește parametrii p și q care reprezintă indicii subvectorului pe care este operată partiția (presupunem întotdeauna $1\leq p\leq q\leq n$ ${\ displaystyle 1 \ leq p \ leq q \ leq n}$ $1 \ leq p \ leq q \ leq n$ ). Celelalte variabile care apar în procedură sunt locale.

 Funcție partiție (A, p, q)
începe
  i ← p
  j ← q
  în timp ce i ≤ j fac
    începe
      în timp ce A [j]> A [p] face j ← j - 1
      în timp ce i ≤ j și A [i] ≤ A [p] fac i ← i + 1
      dacă i <j atunci
         începe
           Schimb (A [i], A [j])
           i ← i + 1
           j ← j - 1
         Sfârșit
    Sfârșit
  Schimb (A [p], A [j])
  întoarce j
Sfârșit

Analiza performanței

Cel mai rău caz

Notăm cu $T_{w}(n)$ ${\ displaystyle T_ {w} (n)}$ $T_ {w} (n)$ numărul maxim de comparații între elementele vectorului de intrare efectuat de algoritmul de pe intrarea A de lungime n. Este evident că vectorii de partiție A1 și A2 pot fi calculați prin intermediul unor comparații n-1 (deoarece un element este ales ca pivot ). Mai mult, dimensiunea A1 și A2 este dată de k și nk-1, pentru unii $k\in [0,1,...,n-1]$ ${\ displaystyle k \ in [0,1, ..., n-1]}$ $k \ in [0,1, ..., n-1]$ . Aceasta implică asta pentru fiecare

$n\geq 1$ ${\ displaystyle n \ geq 1}$ $n \ geq 1$ :

$T_{w}(n)=n-1+max_{0\leq k\leq n-1}{T_{w}(k)+T_{w}(n-k-1)}$ ${\ displaystyle T_ {w} (n) = n-1 + max_ {0 \ leq k \ leq n-1} {T_ {w} (k) + T_ {w} (nk-1)}}$ $T_ {w} (n) = n-1 + max _ {{0 \ leq k \ leq n-1}} {T_ {w} (k) + T_ {w} (n-k-1)}$

în timp ce pentru $n=0$ ${\ displaystyle n = 0}$ $n = 0$ :

$T_{w}(0)=0$ ${\ displaystyle T_ {w} (0) = 0}$ $T_ {w} (0) = 0$ . Aceasta este ecuația recurenței pentru algoritmul în cauză. Acum vrem să determinăm $T_{w}(0)$ ${\ displaystyle T_ {w} (0)}$ $T_ {w} (0)$ corect. În cazul practic, această valoare va fi utilă pentru a înțelege comportamentul algoritmului în cazul în care elementul maxim sau minim este ales pentru partiționare. De fapt de atunci $max_{0\leq k\leq n-1}[T_{w}(k)+T_{w}(n-k-1)]\geq T_{w}(n-1)$ ${\ displaystyle max_ {0 \ leq k \ leq n-1} [T_ {w} (k) + T_ {w} (nk-1)] \ geq T_ {w} (n-1)}$ $max _ {{0 \ leq k \ leq n-1}} [T_ {w} (k) + T_ {w} (n-k-1)] \ geq T_ {w} (n-1)$ avem asta $T_{w}(n)\geq n-1+T_{w}(n-1)$ ${\ displaystyle T_ {w} (n) \ geq n-1 + T_ {w} (n-1)}$ $T_ {w} (n) \ geq n-1 + T_ {w} (n-1)$ și deci pentru fiecare $n\in N$ ${\ displaystyle n \ in N}$ $n \ în N$ noi obținem:

$T_{w}(n)=\sum _{0}^{n-1}k={\frac {n(n-1)}{2}}$ ${\ displaystyle T_ {w} (n) = \ sum _ {0} ^ {n-1} k = {\ frac {n (n-1)} {2}}}$ $T_ {w} (n) = \ sum _ {{0}} ^ {{n-1}} k = {\ frac {n (n-1)} {2}}$ .

În acest fel, am obținut că cel mai rău algoritm de caz are un cost pătratic. Cel mai rău caz apare atunci când dezechilibrul este total, adică atunci când algoritmul de partiționare returnează o partiție de lungime n-1 și una de lungime 0; în acest caz, timpul de execuție este Θ ( $n^{2}$ ${\ displaystyle n ^ {2}}$ $n ^ {2}$ ).

Dacă vrem să evităm că alegerea partiționării ne conduce la un timp pătratic, este suficient să alegem ca pivot elementul median al secvenței, de exemplu prin intermediul algoritmului QuickSelect . Acest lucru ne permite să ne găsim întotdeauna având două secvențe de $\lfloor n/2\rfloor$ ${\ displaystyle \ lfloor n / 2 \ rfloor}$ $\ lfloor n / 2 \ rfloor$ elemente, obținându-se astfel un timp asimptotic egal cu O (nlogn) în cel mai rău caz. La o analiză mai atentă, însă, se dovedește că constanta multiplicativă este de aproximativ 24 (și nu de 1,39, ca în cel mai bun caz). Pentru a observa acest lucru, pur și simplu alegeți pivotul urmând acești pași:

Construiți n / 5 cvintuplu: este posibil ca ultimul subarray să nu fie un cvintuplu, ci un set mai mic;
Pentru fiecare cvintuplu calculați mediana, făcând un total de 7n / 5 comparații, deoarece mediana a 5 elemente poate fi calculată cu cel mult 7 comparații;
Obțineți o probă, obținută ca mediană a medianelor cvintuplurilor;
Calculați pivotul ca mediană a medianelor, luând un timp egal cu T (n / 5) (numit recursiv);
Partiție în jurul pivotului: (n-1) comparații;
Continuați recursiv: T ((7/10) n) (deoarece apelul este făcut un set cu cardinalitate uniformă, cel mult 7n / 10 +3).

Ecuația recurenței devine:

T (n) ≤ (12/5) n + T (n / 5) + T ((7/10) n)

care are soluția O (n), în special T (n) <= cn <-> c> 24. Prin urmare, există soluții aproximative care, în practică, evită cel mai rău caz, deși nu pot garanta acest lucru.

Carcasă medie

Pentru studiul de caz mediu, se evaluează numărul mediu de comparații între elementele vectorului de intrare efectuat de algoritm, determinând astfel ordinea de mărime a timpului mediu de calcul necesar pentru efectuarea procedurii.

Complexitatea algoritmului în acest caz este $O(n\log _{2}(n))$ ${\ displaystyle O (n \ log _ {2} (n))}$ ${\ displaystyle O (n \ log _ {2} (n))}$ .

Cel mai bun caz

Cel mai bun caz apare atunci când algoritmul de partiționare determină două subprobleme perfect echilibrate, ambele cu dimensiunea n / 2 ; în acest caz timpul de execuție este $O(nlog_{2}n)$ ${\ displaystyle O (nlog_ {2} n)}$ ${\ displaystyle O (nlog_ {2} n)}$ , tocmai 1,39nlogn.

Tipuri de partiționare

Există variante ale quicksortului care se bazează pe alegerea diferită a elementului pivot din seria de date de sortat.

Non-random (non-random) : în această versiune se alege elementul din ultima poziție ca pivot, evitându-se astfel calculul alegerii numerelor aleatorii. Cel mai rău caz este un vector ordonat invers. Chiar dacă un alt element este ales ca pivot (de exemplu, primul sau mijlocul), se poate găsi un caz foarte rău.
Metoda medianei : Metoda medianei 3 este o abordare tipică care permite îmbunătățirea partiționării matricei, evitând partițiile prea dezechilibrate și constă în efectuarea partiționării alegând în mod adecvat pivotul din subarray: în special pivotul este ales ca mediană a unui set de trei elemente selectate la întâmplare din subarray. Cu toate acestea, chiar și în acest caz există un caz foarte prost și are o complexitate pătratică.
Aleatoriu : Aceasta este prima versiune publicată a quicksortului, care se bazează pe alegerea aleatorie a elementului pivot. Acest lucru nu ne permite să stabilim la masă care este cel mai rău caz, care totuși va apărea cu probabilitatea O ((1 / n) ^ log n) .

După cum sa menționat mai sus, toate aceste versiuni sunt realizate prin adăugarea unui swap înainte de apelul către partiție, de exemplu:

 alegeți aleatoriu un număr întreg k din p și q
  Schimb (A [p], A [k])
  Partiție (A, p, q)

Chei duplicat

Dacă există elemente repetate în același vector, este posibil să le remediați în prima scanare efectuată de versiunea Bentley - Mc Illroy din 1993. Această versiune prevede că, în timpul procesului de scanare (faza de partiționare a algoritmului), elementele egale cu pivotul sunt mutate imediat în partea pivotului (spre stânga dacă vin din partea stângă, spre dreapta dacă vin din partea dreaptă). În acest fel, voi avea trei partiții, una cu elementele minore ale pivotului, una cu elementele egale și una cu elementele majore ale pivotului.

Complexitatea algoritmului nu este modificată.

Dimensiunea stivei

Algoritmul folosește recursivitatea, care în caz de anomalii ar putea duce la probleme de depășire a stivei . Este posibil să efectuați un proces de eliminare a recursivității fără a afecta performanța utilizând o stivă externă care stochează „lucrările de făcut” sub formă de fișiere parțiale care urmează a fi sortate. Ori de câte ori se solicită sortarea unui subfisier, este suficient să îl extrageți din stivă, în timp ce în urma unei partiționări pot fi inserate cele două fișiere parțiale generate. În implementarea recursivă (cele văzute mai sus), stiva gestionată de sistem conține aceleași informații care vor fi salvate în această stivă externă. Pentru un fișier aleatoriu, dimensiunea maximă a stivei este proporțională cu $\log n$ ${\ displaystyle \ log n}$ $\ log n$ chiar dacă în cazuri degenerate stiva poate crește proporțional cu N. Cel mai rău caz este acela în care fișierul este deja sortat. Această problemă este la fel de subtilă pe cât de reală: chiar și un program recursiv (implicit) folosește o stivă, astfel încât degenerarea rapidă a fișierelor mari ar putea determina terminarea anormală a programului din cauza lipsei de memorie disponibilă. Evident, un astfel de comportament trebuie evitat mai ales dacă doriți să introduceți rutina într-o bibliotecă de programe. Nu este ușor să oferiți garanții că acest lucru nu se va întâmpla chiar dacă nu este dificil să faceți aceste cazuri degenerate extrem de improbabile.

Pentru a efectua studiul dimensiunii stivei, se efectuează o evaluare a spațiului de memorie necesar pentru procedura quicksort. În plus față de n celule necesare pentru a menține vectorul valorilor de intrare, trebuie utilizată o anumită cantitate de spațiu pentru a menține stiva care implementează recursiunea. În cel mai rău caz, Quicksort (1, n) folosește un spațiu $O(n)$ ${\ displaystyle O (n)}$ $Pe)$ pentru a păstra stiva. De fapt, dacă se extrage cel mai mare element al eșantionului, stiva trebuie să păstreze parametrii referitori la un maxim de n - 1 apeluri recursive.

Rapid scurt iterativ

Primul pas pentru a trece de la strategia recursivă la strategia iterativă este să introduceți cel mai mare dintre cele două subfile care urmează a fi sortate în stivă, asigurându-vă că fiecare subfile prezent în stivă nu este mai mare decât jumătate din cel de sub acesta, de aceea stiva nu trebuie să fie conțin mai mult decât un număr logaritmic de obiecte. Această dimensiune maximă a stivei apare atunci când partiționarea se face întotdeauna în centrul fișierului. Pentru fișierele aleatorii, ocuparea stivei este probabil să fie mică.

Versiunea de bază a quicksortului poate fi îmbunătățită modificând intenționat apelurile recursive. Mai precis, procedura poate fi forțată să execute întotdeauna primul apel referitor la subvectorul cu lungime mai mică. Se obține un nou algoritm cu următoarele instrucțiuni (procedura este scrisă în pseudocod):

 Proceduri rapide (A, p, q)
 Intrare Un vector de elemente
   începe
     l ← partiție (A, p, q)
     dacă (l - p) <(q - l) atunci
       începe
         dacă p <(l - 1) atunci Quicksort (A, p, l - 1)
         dacă (l + 1) <q atunci Quicksort (A, l + 1, q)
       Sfârșit
     altceva
       începe
         dacă (l + 1) <q atunci Quicksort (A, l + 1, q)
         dacă p <(l - 1) atunci Quicksort (A, p, l - 1)
       Sfârșit
   Sfârșit

În acest moment este posibil să se efectueze transformarea și să se treacă la versiunea iterativă. În primul rând, se remarcă faptul că, în acest caz, criteriul de gestionare a stivei poate fi simplificat prin exploatarea faptului că cele două apeluri recursive sunt ultimele instrucțiuni ale procedurii. Prin urmare, este posibil să se definească o versiune iterativă în care stiva servește la menținerea listei de apeluri care încă nu au fost executate și nici măcar nu au fost inițiate. Cu alte cuvinte, în execuția procedurii, primul apel recursiv este activat după ce a pus deoparte parametrii necesari pentru executarea celui de-al doilea în partea de sus a stivei. Acesta din urmă va fi activat odată ce precedentul este finalizat, când parametrii săi sunt din nou în partea de sus a stivei. În special, nu este necesar să păstrați înregistrarea activării procedurii în stivă (ceea ce face orice limbaj de programare ori de câte ori este apelată o procedură).

Algoritmul astfel obținut este descris prin următoarea procedură:

 Proceduri Quicksort (A)
 Intrare: un vector A cu datele de sortat
   începe
     p ← 1
     q ← n
     S ← NULL
     repeta
       în timp ce (q - p) ≤ 1 faceți
          începe
            Partiție (A, p, q)
            fie A _{p1, q1} vectorul maxim (A _{p, q} )
            fie A _{p2, q2} vectorul min (A _{p, q} )
            S ← Împingeți (S, (p1, q1))
            p ← p2
            q ← q2
          Sfârșit
     până când (S = NULL) sau (q - p) <1
   Sfârșit

Se poate arăta că procedura este corectă. De fapt, la sfârșitul execuției fiecărei bucle repetate până, părțile vectorului de intrare care nu sunt încă sortate sunt conținute în stiva S sau în A _{p, q} . Verificarea acestei proprietăți este ușoară. În consecință, la ieșirea buclei, condiția (S ≠ NULL) și (q - p) <1 garantează că vectorul de intrare este sortat.

Înălțimea maximă a stivei

În primul rând, se observă că vectorul A _{p, q} pe care funcționează mașina nu este niciodată mai mare decât vectorul din partea de sus a stivei S. Mai mult, cu fiecare increment de S dimensiunea A _{p, q} este redusă cu la cel puțin jumătate. Deci, în timpul calculului, stiva poate conține cel mult $log_{2}N$ ${\ displaystyle log_ {2} N}$ $jurnal_ {2} N$ elemente unde n este dimensiunea intrării.

Rapid scurt mixt recursiv-iterativ

Așa cum este descris pentru Quicksort iterativ, de asemenea, pentru această strategie, primul pas este modificarea procedurii recursive având în vedere faptul că al doilea apel la funcția Quicksort are loc la sfârșitul procedurii, atunci când nu mai este necesară menținerea în stiva informațiile și starea funcției de apelare. Al doilea apel recursiv poate fi apoi transformat într-o buclă în interiorul funcției de apelare însăși, după actualizarea corespunzătoare a parametrilor de intrare. Dacă adăugăm la acest prim pas că primul apel recursiv se face întotdeauna din partea vectorului de sortat care este mai scurt (și, prin urmare, niciodată mai mare de jumătate din vectorul de pornire), această strategie reduce simultan numărul de apeluri recursive și poate utilizați stiva de sistem (fără a fi nevoie să creați una ad-hoc) deoarece limitează adâncimea maximă a stivei, chiar și în cel mai rău caz, la $log_{2}N$ ${\ displaystyle log_ {2} N}$ $jurnal_ {2} N$ elemente.

Este raportată o implementare eficientă în C a strategiei descrise. Codul poate fi compilat pentru a sorta șiruri, numere întregi etc.

 / ********** QuickSort (): sortează vectorul 'list []' ********** /

/ **** Compilați QuickSort pentru șiruri de caractere **** /
#define QS_TYPE char *
#define QS_COMPARE (a, b) (strcmp ((a), (b)))

/ **** Compilați QuickSort pentru numere întregi **** /
// # define QS_TYPE int
// # define QS_COMPARE (a, b) ((a) - (b))

/ **** Compilați QuickSort pentru duble, sortați lista în ordine inversată **** /
// # definește QS_TYPE dublu
// # define QS_COMPARE (a, b) ((b) - (a))

void QuickSort ( lista QS_TYPE [], int beg , int end )
{
    QS_TYPE piv ; QS_TYPE tmp ;
    
    int l , r , p ;

    while ( beg < end ) // Această buclă while va substitui al doilea apel recursiv
    {
        l = implora ; p = ( cer + sfârșit ) / 2 ; r = sfârșit ;

        piv = list [ p ];

        în timp ce ( 1 )
        {
            while (( l <= r ) && ( QS_COMPARE ( list [ l ], piv ) <= 0 )) l ++ ;
            while (( l <= r ) && ( QS_COMPARE ( list [ r ], piv ) > 0 )) r - ;

            dacă ( l > r ) pauză ;

            tmp = list [ l ]; list [ l ] = list [ r ]; list [ r ] = tmp ;

            if ( p == r ) p = l ;
            
            l ++ ; r - ;
        }

        list [ p ] = list [ r ]; list [ r ] = piv ;
        r - ;

        // Selectați partea mai scurtă și recursivitatea apelului. Modificați parametrul de intrare. pentru bucla
        if (( r - beg ) < ( end - l ))   
        {
            QuickSort ( list , beg , r );
            implora = l ;
        }
        altceva
        {
            QuickSort ( listă , l , sfârșit );
            sfârșit = r ;
        }
    }   
}

Corzi și vectori

Selecţie

Notă

^ L. Shustek, Interviu: Un interviu cu CAR Hoare , în com. ACM , vol. 52, nr. 3, 2009, pp. 38-41, DOI : 10.1145 / 1467247.1467261 .
^ Interviul meu Quickshort cu Sir Tony Hoare, inventatorul Quicksort , pe anothercasualcoder.blogspot.com , Marcelo M De Barros, 15 martie 2015.

Bibliografie

Hoare, CAR (1961): Partiție: Algoritm 63 , Quicksort: Algoritm 64 și Find: Algoritm 65. , Comm. ACM 4, pp. 321-322
Sedgewick, Robert (1978): Implementing quicksort programs , Communications of the ACM, 21 (10) pp. 847-857.
Musser, David (1997): Algoritmi de sortare și selecție introspectivă , Software Practice and Experience vol 27, numărul 8, pp. 983–993
LaMarca, A.; Ladner, RE (1997): Influența cache-urilor asupra performanței sortării , lucrările celui de-al optulea simpozion anual ACM-SIAM pe algoritmi discreți, pp. 370–379.

Elemente conexe

qsort - Funcție de sortare găsită în biblioteca standard C , care implementează de obicei algoritmul de sortare quicksort.

Alte proiecte

Wikibooks conține implementări rapide
Wikimedia Commons conține imagini sau alte fișiere pe scurt

linkuri externe

Quicksort interactiv , pe pages.stern.nyu.edu .
Multidimensional quicksort în Java , la fiehnlab.ucdavis.edu . Adus la 26 decembrie 2005 (arhivat din original la 24 noiembrie 2005) .

Portal IT : accesați intrările Wikipedia care se ocupă cu IT

[1] L. Shustek, Interviu: Un interviu cu CAR Hoare , în com. ACM , vol. 52, nr. 3, 2009, pp. 38-41, DOI : 10.1145 / 1467247.1467261 .

[2] Interviul meu Quickshort cu Sir Tony Hoare, inventatorul Quicksort , pe anothercasualcoder.blogspot.com , Marcelo M De Barros, 15 martie 2015.

[1]

[2]

V · D · M Algoritmi de sortare
Teorie	Teoria complexității de calcul · notație Big O · Matrice · Listă · Stivă · Coadă · Sortare comparativă · Sortare adaptivă
Algoritmi de schimb	Bubble sortare · Shaker sortare · par-impar sortare · Comb sortare · Gnome sortare · Quicksort
Algoritmi de selecție	Sortare selecție · Sortare grămadă · Smoothsort
Algoritmi de inserție	Inserția sortare · Shell sortare · copac sortare · Bibliotecă sortare · sortare Răbdare
Algoritmi de fuziune	Merge sort · Timsort
Algoritmi necomparativi	Sortare Radix · Sortare cupă · Sortare numărare · Sortare porumbel
Alți algoritmi	Sortarea de rețea · topologică sortare · sortare bitonic · clatite sortare
Algoritmi ineficienți	Sortare stupidă · Sortare Trippel