Combinarea rezultatelor — pasul care decide viteza

Ce este pasul de combinare

Divide et impera are trei pași: împarți problema, rezolvi fiecare bucată, apoi combini rezultatele parțiale într-un răspuns pentru întreg. Împărțirea și rezolvarea bucăților le-am tratat în lecțiile anterioare. Aici ne ocupăm de al treilea pas — cel care lipește la loc.

Combinarea pare uneori un detaliu, dar de cele mai multe ori el este partea cea mai costisitoare și, mai important, el decide complexitatea totală. Logica e simplă: arborele recursiei are aproximativ log n niveluri (la fiecare nivel problema se înjumătățește). Pe fiecare nivel, combinarea trebuie să atingă, în total, toate cele n elemente. Deci costul global este „cât face combinarea pe un nivel” înmulțit cu „câte niveluri sunt”. Dacă pe fiecare nivel combinarea costă O(n), ai O(n) × O(log n) = O(n log n). Dacă reușești să combini mai ieftin sau, dimpotrivă, combini scump, ordinul total se schimbă odată cu pasul de combinare.

Exemplu pas cu pas: interclasarea

Avem două jumătăți deja sortate: stânga [2, 5, 8] și dreapta [1, 3, 9]. Vrem un singur vector sortat. Folosim doi pointeri: i pe stânga, j pe dreapta, fiecare pornind de la primul element al jumătății lui. La fiecare pas comparăm stanga[i] cu dreapta[j], luăm valoarea mai mică și avansăm pointerul ei.

• i=0 (2), j=0 (1): 1 < 2, iau 1, avansez j. Rezultat: [1]
• i=0 (2), j=1 (3): 2 < 3, iau 2, avansez i. Rezultat: [1, 2]
• i=1 (5), j=1 (3): 3 < 5, iau 3, avansez j. Rezultat: [1, 2, 3]
• i=1 (5), j=2 (9): 5 < 9, iau 5, avansez i. Rezultat: [1, 2, 3, 5]
• i=2 (8), j=2 (9): 8 < 9, iau 8, avansez i. Rezultat: [1, 2, 3, 5, 8]
• i a ieșit din stânga: copiez restul dreptei (9). Rezultat: [1, 2, 3, 5, 8, 9]

Am parcurs fiecare element exact o dată: șase elemente, șase pași. De aici vine costul liniar al combinării.

Implementare C++

Funcția de mai jos interclasează două porțiuni sortate ale aceluiași vector — [st, mid] și [mid + 1, dr] — într-un vector auxiliar, apoi copiază înapoi. Presupune că ambele porțiuni sunt deja sortate (rezolvarea lor e subiectul altei lecții).

#include <iostream>
using namespace std;

// interclaseaza portiunile sortate [st, mid] si [mid+1, dr] din a[]
void interclaseaza(int a[], int st, int mid, int dr) {
    int aux[100];              // vector auxiliar pentru rezultatul interclasat
    int i = st;                // pointer pe jumatatea stanga [st, mid]
    int j = mid + 1;           // pointer pe jumatatea dreapta [mid+1, dr]
    int k = 0;                 // pozitia curenta in aux

    // cat timp ambele jumatati mai au elemente, ia minimul dintre varfuri
    while (i <= mid && j <= dr) {
        if (a[i] <= a[j]) {
            aux[k] = a[i];
            i++;
        } else {
            aux[k] = a[j];
            j++;
        }
        k++;
    }

    // copiaza ce a ramas in stanga (daca a ramas ceva)
    while (i <= mid) {
        aux[k] = a[i];
        i++;
        k++;
    }
    // copiaza ce a ramas in dreapta (daca a ramas ceva)
    while (j <= dr) {
        aux[k] = a[j];
        j++;
        k++;
    }

    // pune rezultatul sortat inapoi in a[st..dr]
    for (int t = 0; t < k; t++) {
        a[st + t] = aux[t];
    }
}

int main() {
    // a[0..2] = {2,5,8} sortat, a[3..5] = {1,3,9} sortat
    int a[] = {2, 5, 8, 1, 3, 9};
    interclaseaza(a, 0, 2, 5);   // mid = 2, deci [0,2] si [3,5]
    for (int t = 0; t < 6; t++) {
        cout << a[t] << " ";     // 1 2 3 5 8 9
    }
    cout << endl;
    return 0;
}

Rezultatul afișat este 1 2 3 5 8 9 — cele două jumătăți sortate, împletite într-un singur vector sortat, fără să comparăm fiecare element cu fiecare.

Complexitate

Pe fiecare nivel al recursiei, suma lungimilor tuturor porțiunilor interclasate este n, deci munca de combinare per nivel este O(n). Cu log n niveluri rezultă O(n log n) — exact complexitatea lui Merge Sort, dictată de pasul de combinare.

Recapitulare

• Combinarea e al treilea pas: din rezultate parțiale, deja ordonate, faci un răspuns pentru întreg — clasic, interclasarea a două jumătăți sortate cu doi pointeri.
• Costă O(n) pe un nivel (atinge fiecare element o dată); cu log n niveluri rezultă O(n log n) — pasul de combinare decide ordinul total.
• Atenție la capete: dreapta începe la mid + 1, condițiile includ ambele capete și copiezi întotdeauna ce rămâne dintr-o jumătate după ce cealaltă s-a golit.