Sortare Rapidă (Quick Sort) în C++

Principiul Algoritmului

Quick Sort alege un element pivot și partiționează vectorul astfel încât elementele mai mici să fie la stânga, iar cele mai mari la dreapta pivotului.

Implementare

Copiază
1#include <iostream>
2#include <vector>
3using namespace std;
4
5int partitie(vector<int>& v, int st, int dr) {
6    int pivot = v[dr]; // Alegem ultimul element ca pivot
7    int i = st - 1;
8    
9    for (int j = st; j < dr; j++) {
10        if (v[j] < pivot) {
11            i++;
12            swap(v[i], v[j]);
13        }
14    }
15    swap(v[i + 1], v[dr]);
16    return i + 1;
17}
18
19void quickSort(vector<int>& v, int st, int dr) {
20    if (st < dr) {
21        int poz_pivot = partitie(v, st, dr);
22        quickSort(v, st, poz_pivot - 1);
23        quickSort(v, poz_pivot + 1, dr);
24    }
25}
26
27int main() {
28    vector<int> v = {64, 34, 25, 12, 22, 11, 90};
29    
30    cout << "Vector initial: ";
31    for (int x : v) cout << x << " ";
32    cout << endl;
33    
34    quickSort(v, 0, v.size() - 1);
35    
36    cout << "Vector sortat: ";
37    for (int x : v) cout << x << " ";
38    cout << endl;
39    
40    return 0;
41}

Alegerea Pivotului

Copiază
1// Metoda Median of Three
2int medianOfThree(vector<int>& v, int st, int dr) {
3    int mid = st + (dr - st) / 2;
4    
5    if (v[st] > v[mid]) swap(v[st], v[mid]);
6    if (v[st] > v[dr]) swap(v[st], v[dr]);
7    if (v[mid] > v[dr]) swap(v[mid], v[dr]);
8    
9    swap(v[mid], v[dr - 1]);
10    return v[dr - 1];
11}

Complexitate

Avantaje

• •In-place (nu necesită memorie suplimentară semnificativă)
• •Cache-friendly
• •Rapid în practică