Sortarea rapidă

Sortarea rapidă, numită și quicksort, alege un pivot și separă valorile mai mici de cele mai mari, apoi sortează recursiv părțile. Din $[5,2,4]$, un pivot 4 poate separa 2 în stânga și 5 în dreapta, obținând $[2,4,5]$. O partiționare corectă trebuie să reducă problema la fiecare apel.

Partiționarea

Pentru secvența v[st..dr] alegi pivotul p = v[(st + dr) / 2]. Indicele i pornește de la st și avansează cât timp v[i] < p; indicele j pornește de la dr și coboară cât timp v[j] > p. Când amândoi s-au oprit, v[i] este prea mare pentru stânga, iar v[j] prea mic pentru dreapta: îi interschimbi și continui. Când i trece de j, secvența st..j conține numai valori cel mult egale cu p, iar secvența i..dr numai valori cel puțin egale cu p.

Recursivitatea

După partiționare, cele două părți se sortează independent, cu același subprogram, iar combinarea nu mai cere nimic: odată sortate părțile, tot vectorul este sortat. Este schema divide et impera, cu munca făcută la descompunere, spre deosebire de sortarea prin interclasare, unde munca se face la combinare.

void qs(int v[], int st, int dr) {
    int i = st, j = dr, p = v[(st + dr) / 2];
    while (i <= j) {
        while (v[i] < p) i++;
        while (v[j] > p) j--;
        if (i <= j) {
            int aux = v[i]; v[i] = v[j]; v[j] = aux;
            i++;
            j--;
        }
    }
    if (st < j) qs(v, st, j);
    if (i < dr) qs(v, i, dr);
}

De ce e rapid și când nu e

Dacă pivotul împarte de fiecare dată secvența în două părți apropiate ca mărime, sunt aproximativ ${\log }_{2}n$ niveluri de împărțire, iar fiecare nivel parcurge în total cel mult n elemente: de aici ordinul $n{\log }_{2}n$. Dacă pivotul este mereu cea mai mică sau cea mai mare valoare, o parte rămâne goală, nivelurile devin n, iar numărul de comparații ajunge la ordinul $n^2$. Alegerea pivotului din mijloc evită acest caz pentru vectorii deja sortați, unde pivotul ales ca prim element ar fi cea mai proastă alegere (exemplul 7). În biblioteca algorithm există funcția sort, care sortează în medie la fel de rapid; enunțurile care cer o metodă anume trebuie însă rezolvate cu metoda cerută.

O variantă de partiționare: pivotul la capăt

Quicksort este o aplicație a metodei divide et impera: partiționarea pune elementele cel mult egale cu pivotul înaintea lui și pe cele mai mari după el, apoi sortează recursiv cele două segmente; nu există o etapă separată de interclasare. În varianta de mai jos pivotul este ultimul element al segmentului și ajunge la poziția lui finală, deci apelurile recursive sortează doar segmentele din stânga și din dreapta lui.

#include <iostream>
using namespace std;
void quicksort(int v[], int st, int dr) {
    if (st >= dr) return;
    int pivot = v[dr], i = st;
    for (int j = st; j < dr; ++j)
        if (v[j] <= pivot) {
            int t = v[i]; v[i] = v[j]; v[j] = t;
            ++i;
        }
    int t = v[i]; v[i] = v[dr]; v[dr] = t;
    quicksort(v, st, i - 1);
    quicksort(v, i + 1, dr);
}
int main() {
    int v[] = {5, 2, 4, 1, 3};
    quicksort(v, 0, 4);
    for (int i = 0; i < 5; ++i) cout << v[i] << " ";
    return 0;
}

Programul afișează 1 2 3 4 5. Pentru acest tablou algoritmul face 6 comparații în partiționări; pentru tabloul $5,2,7,1,3,6,8,4$ face 15.

Invariantul partiționării. La începutul fiecărei iterații j, elementele v[st..i-1] sunt cel mult egale cu pivotul, iar v[i..j-1] sunt mai mari decât el. Un element v[j] <= pivot ocupă prima poziție a zonei „mai mari” prin schimb, iar i crește; altfel j doar înaintează. Exemplul 1 — cazul cel mai defavorabil. Pentru tabloul deja sortat $1,2,3,4,5$ și pivotul ales ultimul, fiecare partiționare lasă toate celelalte elemente de aceeași parte: pivotul 5 este maximul, segmentul din stânga are 4 elemente, apoi 3 și așa mai departe. Comparațiile sunt $4+3+2+1=10$, iar pentru un tablou sortat cu 8 elemente sunt $7+6+\dots +1=28$. Adâncimea recursivității este $n-1$, ceea ce poate umple stiva pentru tablouri foarte mari. Un pivot ales la mijlocul segmentului sau o schimbare inițială cu elementul din mijloc evită acest caz pentru tablourile sortate.

Exemplul 2 — elemente egale. Testul v[j] <= pivot pune elementele egale cu pivotul în partea stângă. Pentru $3,3,3$ cu pivotul 3, toate elementele satisfac testul, i ajunge la ultima poziție, iar segmentul din dreapta este gol: apelurile recursive reduc problema de fiecare dată cu un singur element. Șirurile cu multe valori egale pot fi astfel încetinite.

Exemple rezolvate

Exemplul 3: o partiționare, pas cu pas

Partiționează vectorul 7, 2, 9, 4, 1, 8, 3 (pozițiile 0…6) în jurul pivotului din mijloc.

1. Pivotul este v[3] = 4.
2. i se oprește la 7 (poziția 0), j se oprește la 3 (poziția 6): interschimbi și obții 3, 2, 9, 4, 1, 8, 7; i = 1, j = 5.
3. i trece de 2 și se oprește la 9 (poziția 2); j trece de 8 și se oprește la 1 (poziția 4): interschimbi și obții 3, 2, 1, 4, 9, 8, 7; i = 3, j = 3.
4. Amândoi se opresc la pivotul 4; interschimbarea lui cu el însuși nu schimbă nimic, iar i = 4, j = 2. Bucla se termină.
5. Rezultatul: 3, 2, 1 în stânga (st..j = 0..2), 9, 8, 7 în dreapta (i..dr = 4..6), cu 4 între ele, deja la locul lui.

#include <iostream>
using namespace std;

int main() {
    int v[] = {7, 2, 9, 4, 1, 8, 3}, st = 0, dr = 6;
    int i = st, j = dr, p = v[(st + dr) / 2];
    while (i <= j) {
        while (v[i] < p) i++;
        while (v[j] > p) j--;
        if (i <= j) {
            int aux = v[i]; v[i] = v[j]; v[j] = aux;
            i++;
            j--;
        }
    }
    for (int k = 0; k < 7; k++)
        cout << v[k] << " ";
    cout << "\ni=" << i << " j=" << j << "\n";
    return 0;
}

Programul afișează:

3 2 1 4 9 8 7
i=4 j=2

Exemplul 4: sortarea completă

Se citesc n ≤ 1000 și n numere întregi. Afișează-le în ordine crescătoare, sortate cu quicksort.

#include <iostream>
using namespace std;

int v[1000];

void qs(int st, int dr) {
    int i = st, j = dr, p = v[(st + dr) / 2];
    while (i <= j) {
        while (v[i] < p) i++;
        while (v[j] > p) j--;
        if (i <= j) {
            int aux = v[i]; v[i] = v[j]; v[j] = aux;
            i++;
            j--;
        }
    }
    if (st < j) qs(st, j);
    if (i < dr) qs(i, dr);
}

int main() {
    int n;
    cin >> n;
    for (int k = 0; k < n; k++)
        cin >> v[k];
    qs(0, n - 1);
    for (int k = 0; k < n; k++)
        cout << v[k] << " ";
    cout << "\n";
    return 0;
}

Pentru intrarea 7 și 7 2 9 4 1 8 3, programul afișează:

1 2 3 4 7 8 9

Exemplul 5: ordine descrescătoare

Pentru ordinea descrescătoare schimbi doar cele două comparații cu pivotul: i avansează cât timp v[i] > p, iar j coboară cât timp v[j] < p. Pentru același vector, rezultatul este 9, 8, 7, 4, 3, 2, 1.

#include <iostream>
using namespace std;

int v[] = {7, 2, 9, 4, 1, 8, 3};

void qsd(int st, int dr) {
    int i = st, j = dr, p = v[(st + dr) / 2];
    while (i <= j) {
        while (v[i] > p) i++;
        while (v[j] < p) j--;
        if (i <= j) {
            int aux = v[i]; v[i] = v[j]; v[j] = aux;
            i++;
            j--;
        }
    }
    if (st < j) qsd(st, j);
    if (i < dr) qsd(i, dr);
}

int main() {
    qsd(0, 6);
    for (int k = 0; k < 7; k++)
        cout << v[k] << " ";
    cout << "\n";
    return 0;
}

9 8 7 4 3 2 1

Exemplul 6: al k-lea cel mai mic element, fără sortare completă

Află al treilea cel mai mic element al vectorului 7, 2, 9, 4, 1, 8, 3.

1. După o partiționare, toate valorile din st..j sunt cel mult egale cu cele din i..dr. Dacă poziția căutată, k − 1 = 2, este în st..j, continui doar în stânga; dacă este în i..dr, doar în dreapta; altfel, elementul de pe ea e deja la locul lui.
2. Prima partiționare dă 3, 2, 1 | 4 | 9, 8, 7, cu j = 2: poziția 2 este în stânga, deci continui pe 3, 2, 1, unde partiționarea o pune pe 3 pe poziția 2.
3. Răspunsul este 3. Se lucrează pe o singură parte la fiecare pas, deci în medie de ordinul n operații.

#include <iostream>
using namespace std;

int v[] = {7, 2, 9, 4, 1, 8, 3};

int alKlea(int st, int dr, int poz) {
    while (st < dr) {
        int i = st, j = dr, p = v[(st + dr) / 2];
        while (i <= j) {
            while (v[i] < p) i++;
            while (v[j] > p) j--;
            if (i <= j) {
                int aux = v[i]; v[i] = v[j]; v[j] = aux;
                i++;
                j--;
            }
        }
        if (poz <= j) dr = j;          // continui in stanga
        else if (poz >= i) st = i;     // continui in dreapta
        else break;                    // poz este intre j si i: e la locul lui
    }
    return v[poz];
}

int main() {
    cout << alKlea(0, 6, 2) << "\n";   // al 3-lea cel mai mic: pozitia 2
    return 0;
}

Programul afișează:

3

Exemplul 7: nivel de examen, cel mai rău caz

O variantă de quicksort alege ca pivot primul element al secvenței și îl compară cu fiecare dintre celelalte. Câte comparații cu pivotul face pe vectorul deja sortat 1, 2, …, 10?

1. Pivotul 1 este cel mai mic, deci partea din stânga rămâne goală, iar cea din dreapta are 9 elemente: 9 comparații.
2. La fel la fiecare nivel: 8, 7, …, 1 comparații.
3. Total: 9 + 8 + … + 1 = 45 = 10 · 9 / 2, adică ordinul $n^2$.

#include <iostream>
using namespace std;

int v[11], nrc = 0;

void qsPrim(int st, int dr) {          // pivotul este v[st]
    if (st >= dr) return;
    int p = v[st], k = st;
    for (int i = st + 1; i <= dr; i++) {
        nrc++;                         // o comparatie cu pivotul
        if (v[i] < p) {
            k++;
            int aux = v[k]; v[k] = v[i]; v[i] = aux;
        }
    }
    int aux = v[st]; v[st] = v[k]; v[k] = aux;   // pivotul pe locul lui
    qsPrim(st, k - 1);
    qsPrim(k + 1, dr);
}

int main() {
    for (int i = 1; i <= 10; i++)
        v[i] = i;
    qsPrim(1, 10);
    cout << nrc << "\n";
    return 0;
}

Programul afișează:

45

Cu pivotul din mijloc, ca în exemplele 3–6, vectorul sortat se împarte de fiecare dată în două jumătăți, iar acest caz nu mai este cel rău.

Greșeli frecvente

• Greșit: după partiționarea cu doi indici, cele două segmente sunt deja sortate.
  Corect: partiționarea le separă după valoarea pivotului; fiecare segment se sortează recursiv.
• Greșit: quicksort face mereu $n\log n$ comparații.
  Corect: în cel mai defavorabil caz face $n(n-1)/2$.
• Greșit: în varianta cu doi indici se exclud din autoapeluri pozițiile pivotului ales inițial.
  Corect: se sortează segmentele st..j și i..dr; doar varianta cu pivotul la capăt îl așază pe locul final și îl exclude din autoapeluri.
• Greșit: condițiile <= în buclele de avans din partiționarea cu doi indici, de exemplu while (v[i] <= p).
  Corect: indicele i poate trece de capătul secvenței când pivotul este cea mai mare valoare, deci comparațiile cu pivotul sunt stricte.
• Greșit: se uită i++ și j-- după interschimbare.
  Corect: fără ele, dacă v[i] și v[j] sunt egale cu pivotul, bucla nu mai avansează.
• Greșit: autoapelurile se fac pe secvențele de dinainte de partiționare.
  Corect: părțile sunt st..j și i..dr, cu indicii de după partiționare.
• Greșit: pivotul ales ca prim element pe date sortate.
  Corect: duce la ordinul $n^2$ (exemplul 7); alegi elementul din mijloc.
• Greșit: quicksort se folosește când se cere stabilitate.
  Corect: partiționarea nu păstrează ordinea valorilor egale.
• Greșit: pivotul ajunge neapărat în mijlocul tabloului.
  Corect: poziția lui depinde de valori.
• Greșit: orice alegere a pivotului garantează timp $n\log n$.
  Corect: există cazuri cu timp pătratic.
• Greșit: în varianta cu pivotul la capăt, apelurile recursive includ din nou poziția finală a pivotului.
  Corect: sortează doar segmentele din stânga și din dreapta lui.

Înainte și după

Întrebări frecvente