Merge Sort și Quick Sort în C++: comparație și cod

Merge Sort și Quick Sort sunt algoritmi de sortare bazați pe divide et impera. Primul sortează jumătățile și apoi le interclasează; al doilea separă valorile în jurul unui pivot și continuă în subintervale. Asemănarea recursivă nu înseamnă aceleași garanții de timp și memorie.

Vom ordona crescător numere întregi, păstrând toate aparițiile. Exemplele acceptă și valori egale, numere negative sau un șir gol. Alegerea unui algoritm depinde de limite, stabilitate și memoria disponibilă.

Cum funcționează

Merge Sort: împărțire și interclasare

Pentru intervalul inclusiv [l,r], cazul de bază este l>=r. Altfel calculăm mijlocul fără adunarea directă l+r, sortăm cele două jumătăți și le interclasăm într-un tablou auxiliar. Doi indici urmăresc primele elemente încă neconsumate. Copiem de fiecare dată minimul și apoi restul jumătății neepuizate. La final transferăm rezultatul în intervalul inițial.

Comparația <= alege mai întâi elementul din stânga în caz de egalitate. Aceasta păstrează ordinea inițială a elementelor egale, deci implementarea este stabilă. Proprietatea devine vizibilă când sortăm înregistrări după o singură cheie, păstrând și alte câmpuri.

Quick Sort: partiționare și pivot

Alegem valoarea din mijloc ca pivot. Un indice avansează peste valori mai mici, celălalt se retrage peste valori mai mari. Când se întâlnesc valori aflate în părțile nepotrivite, le schimbăm. După schimb avansăm ambii indici inclusiv pentru valori egale, astfel încât algoritmul progresează.

După partiționare, subintervalele rămase pot fi sortate independent. Implementarea apelează recursiv numai partea mai mică și continuă iterativ în partea mai mare. Această optimizare limitează adâncimea stivei, dar nu elimină timpul pătratic din cazurile nefavorabile.

Ambele programe presupun 0 <= n <= 100000 și valori care încap în int. Capacitatea tabloului este 100000, indicii logici 0..n-1. Variantele vector păstrează aceeași capacitate și aceleași intervale; nu schimbă algoritmii. Interclasarea are un al doilea spațiu de lucru, în timp ce partiționarea schimbă elementele direct în tablou.

Exemplu urmărit pas cu pas

Pentru 3,1,3,-2,0, Merge Sort ajunge la intervale de un element și reconstruiește succesiv intervale ordonate. În ultima interclasare, compară mereu minimele rămase ale celor două jumătăți; rezultatul este -2,0,1,3,3.

Quick Sort poate alege pivotul 3, mutând valorile mai mici spre stânga. Poziția finală a pivotului nu este urmărită explicit în această schemă: importante sunt cele două intervale rezultate. Pentru 2,2,2,2, schimburile dintre valori egale par inutile, dar avansarea indicilor asigură terminarea.

Implementare C++17

Merge Sort

Varianta cu tablou clasic:

#include <iostream>
int a[100000], aux[100000];
void mergeSort(int l, int r) {
    if (l >= r)
        return;
    int m = l + (r - l) / 2;
    mergeSort(l, m);
    mergeSort(m + 1, r);
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r) {
        if (a[i] <= a[j])
            aux[k++] = a[i++];
        else
            aux[k++] = a[j++];
    }
    while (i <= m)
        aux[k++] = a[i++];
    while (j <= r)
        aux[k++] = a[j++];
    for (i = l; i <= r; ++i)
        a[i] = aux[i];
}
int main() {
    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    mergeSort(0, n - 1);
    for (int i = 0; i < n; ++i)
        std::cout << a[i] << (i + 1 == n ? '\n' : ' ');
    if (n == 0)
        std::cout << '\n';
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
std::vector<int> a(100000), aux(100000);
void mergeSort(int l, int r) {
    if (l >= r)
        return;
    int m = l + (r - l) / 2;
    mergeSort(l, m);
    mergeSort(m + 1, r);
    int i = l, j = m + 1, k = l;
    while (i <= m && j <= r) {
        if (a[i] <= a[j])
            aux[k++] = a[i++];
        else
            aux[k++] = a[j++];
    }
    while (i <= m)
        aux[k++] = a[i++];
    while (j <= r)
        aux[k++] = a[j++];
    for (i = l; i <= r; ++i)
        a[i] = aux[i];
}
int main() {
    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    mergeSort(0, n - 1);
    for (int i = 0; i < n; ++i)
        std::cout << a[i] << (i + 1 == n ? '\n' : ' ');
    if (n == 0)
        std::cout << '\n';
}

Quick Sort

Varianta cu tablou clasic:

#include <algorithm>
#include <iostream>
int a[100000];
void quickSort(int l, int r) {
    while (l < r) {
        int i = l, j = r, pivot = a[l + (r - l) / 2];
        while (i <= j) {
            while (a[i] < pivot)
                ++i;
            while (a[j] > pivot)
                --j;
            if (i <= j) {
                std::swap(a[i], a[j]);
                ++i;
                --j;
            }
        }
        if (j - l < r - i) {
            if (l < j)
                quickSort(l, j);
            l = i;
        } else {
            if (i < r)
                quickSort(i, r);
            r = j;
        }
    }
}
int main() {
    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    quickSort(0, n - 1);
    for (int i = 0; i < n; ++i)
        std::cout << a[i] << (i + 1 == n ? '\n' : ' ');
    if (n == 0)
        std::cout << '\n';
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <algorithm>
#include <iostream>
#include <vector>
std::vector<int> a(100000);
void quickSort(int l, int r) {
    while (l < r) {
        int i = l, j = r, pivot = a[l + (r - l) / 2];
        while (i <= j) {
            while (a[i] < pivot)
                ++i;
            while (a[j] > pivot)
                --j;
            if (i <= j) {
                std::swap(a[i], a[j]);
                ++i;
                --j;
            }
        }
        if (j - l < r - i) {
            if (l < j)
                quickSort(l, j);
            l = i;
        } else {
            if (i < r)
                quickSort(i, r);
            r = j;
        }
    }
}
int main() {
    int n;
    std::cin >> n;
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    quickSort(0, n - 1);
    for (int i = 0; i < n; ++i)
        std::cout << a[i] << (i + 1 == n ? '\n' : ' ');
    if (n == 0)
        std::cout << '\n';
}

De ce funcționează și cât costă

La Merge Sort, inducția pe lungime garantează că jumătățile sunt sortate, iar interclasarea alege de fiecare dată minimul rămas. La Quick Sort, partiționarea separă intervalele astfel încât valorile din stânga nu depășesc pivotul, iar cele din dreapta nu sunt sub pivot; sortarea lor finalizează ordonarea.

Merge Sort are O(n log n) timp în cazul general și O(n) memorie auxiliară, plus stiva O(log n). Quick Sort are O(n log n) timp în medie pentru partiționări favorabile, dar O(n²) în cel mai rău caz. Varianta prezentată folosește O(log n) stivă prin recursia pe partea mai mică. Nu presupunem o garanție de timp logaritmic doar din alegerea pivotului central.

Greșeli frecvente

Nu confunda poziția centrală cu valoarea mediană a tuturor elementelor. Nu omite avansarea indicilor pentru valori egale. În Merge Sort, copiază și coada jumătății rămase. Pentru n=0, cazul de bază trebuie verificat înainte de accesarea pivotului.

Exersează

Interclasează manual 1,4,4 cu 2,4. Marchează din ce jumătate provine fiecare valoare 4.

Rezolvare explicată: Rezultatul este 1,2,4,4,4. Cu regula <=, cele două valori 4 din stânga apar înaintea valorii 4 din dreapta, păstrând ordinea lor inițială.

Continuă să înveți

Interclasare, divide et impera și complexitate.

Întrebări frecvente

Care algoritm garantează O(n log n)?

Merge Sort, în implementarea prezentată. Quick Sort poate ajunge la O(n²) când partiționările sunt foarte dezechilibrate.

Care variantă este stabilă?

Merge Sort este stabil aici deoarece egalitățile sunt preluate mai întâi din jumătatea stângă. Quick Sort cu schimburi la distanță nu păstrează în general ordinea elementelor egale.

Pivotul din mijloc evită orice caz nefavorabil?

Nu. Alegem o poziție centrală, nu mediana valorilor. Anumite ordonări ale datelor pot produce în continuare partiționări dezechilibrate.

De ce recursia Quick Sort intră în partea mai mică?

Partea apelată recursiv are cel mult aproximativ jumătate din intervalul curent. Partea mare este procesată prin buclă, ceea ce limitează stiva fără a schimba limita de timp nefavorabilă.

Pot folosi std::sort într-o problemă?

Dacă cerința permite biblioteca standard, da. Tot trebuie să înțelegi intervalul semi-deschis transmis, comparatorul și faptul că std::sort nu garantează stabilitate.