Sortarea rapidă (Quick Sort)

Sortarea rapidă (Quick Sort) este un algoritm eficient de sortare bazat pe paradigma divide și cucerește. Iată o implementare în C++ a algoritmului de sortare rapidă:

#include <iostream>

// Funcție pentru a schimba două elemente într-un tablou
void swap(int& a, int& b) {
    int temp = a;
    a = b;
    b = temp;
}

// Funcție pentru a alege un pivot și a rearanja elementele în jurul pivotului
int partition(int lista[], int stanga, int dreapta) {
    int pivot = lista[dreapta];
    int i = stanga - 1;

    for (int j = stanga; j < dreapta; j++) {
        if (lista[j] <= pivot) {
            i++;
            swap(lista[i], lista[j]);
        }
    }

    swap(lista[i + 1], lista[dreapta]);
    return i + 1;
}

// Funcție principală pentru sortarea rapidă
void quickSort(int lista[], int stanga, int dreapta) {
    if (stanga < dreapta) {
        int pivotIndex = partition(lista, stanga, dreapta);

        // Sortare separată pentru subtablourile din stânga și dreapta pivotului
        quickSort(lista, stanga, pivotIndex - 1);
        quickSort(lista, pivotIndex + 1, dreapta);
    }
}

// Funcție pentru a afișa un tablou
void afisareLista(int lista[], int lungime) {
    for (int i = 0; i < lungime; i++) {
        std::cout << lista[i] << " ";
    }
    std::cout << std::endl;
}

int main() {
    int lista[] = {5, 1, 9, 3, 7};
    int lungime = sizeof(lista) / sizeof(lista[0]);

    std::cout << "Lista initiala: ";
    afisareLista(lista, lungime);

    quickSort(lista, 0, lungime - 1);

    std::cout << "Lista sortata: ";
    afisareLista(lista, lungime);

    return 0;
}

Această implementare a sortării rapide folosește o strategie divide et impera. Funcția partition alege un pivot și rearanjează elementele astfel încât cele mai mici să fie în stânga pivotului, iar cele mai mari să fie în dreapta pivotului. Apoi, sortarea rapidă este aplicată recursiv la subtablourile rezultate în stânga și dreapta pivotului.

Exemplu Sortarea rapidă (Quick Sort)

Să simulăm pașii algoritmului de sortare rapidă pentru exemplul valoric {12, 7, 9, 4, 3, 2, 8, 1, 6}.

Pasul 1:

Alegem un pivot. În acest exemplu, vom alege ultimul element, adică 6. Lista este: {12, 7, 9, 4, 3, 2, 8, 1, |6|}.

Pasul 2:

Rearanjăm elementele astfel încât cele mai mici să fie în stânga pivotului, iar cele mai mari în dreapta.

• Comparăm 12 cu 6 – nu schimbăm, continuăm.
• Comparăm 7 cu 6 – nu schimbăm, continuăm.
• Comparăm 9 cu 6 – nu schimbăm, continuăm.
• Comparăm 4 cu 6 – nu schimbăm, continuăm.
• Comparăm 3 cu 6 – nu schimbăm, continuăm.
• Comparăm 2 cu 6 – nu schimbăm, continuăm.
• Comparăm 8 cu 6 – schimbăm locurile, lista devine {6, 7, 9, 4, 3, 2, |8|, 1, 12}.
• Comparăm 1 cu 6 – schimbăm locurile, lista devine {1, 7, 9, 4, 3, 2, 8, |6|, 12}.

La sfârșitul acestui pas, pivotul (6) se află pe poziția corectă. Sublista din stânga pivotului conține elemente mai mici, iar cea din dreapta conține elemente mai mari.

Pasul 3:

Aplicăm recursiv algoritmul pe cele două subliste generate:

• Pe sublista din stânga pivotului {1, 7, 9, 4, 3, 2, 8}, unde noul pivot este 2.
• Pe sublista din dreapta pivotului {8, 12}, unde noul pivot este 12.

Repetăm pașii pentru fiecare sublistă până când întreaga listă este sortată.

Pasul 4:

Continuăm cu sortarea subliste:

Pentru sublista {1, 7, 9, 4, 3, 2, 8}:

Alegem ca pivot ultimul element (8). Rearanjăm sublista și obținem {1, 7, |2|, 4, 3, |8|, 9}. Sublista din stânga pivotului {1, 7, 2, 4, 3} și cea din dreapta {8, 9}.

Pentru sublista {8, 12}:

Sublista este deja sortată.

Pasul 5:

Continuăm aplicarea algoritmului pe subliste până când întreaga listă este sortată.

Rezultat final:

La final, lista este complet sortată: {1, 2, 3, 4, 6, 7, 8, 9, 12}.