Interclasarea a doi vectori sortați

Am învățat să sortăm un vector și să căutăm eficient într-unul sortat. Acum vom vedea cum combinăm doi vectori sortați într-un singur vector, tot sortat.

Această operație se numește interclasare.

Ce este interclasarea?

Având doi vectori sortați crescător, construim un al treilea vector care conține toate elementele din ambii, tot în ordine crescătoare.

Exemplu:

a:  2  5  8  12
b:  3  7  9  15  20

Rezultat:  2  3  5  7  8  9  12  15  20

Ideea algoritmului

Ne imaginăm că avem două cozi de numere, fiecare sortată. La fiecare pas:

1. Ne uităm la primul element din fiecare coadă.
2. Îl luăm pe cel mai mic și îl punem în rezultat.
3. Avansăm în coada din care am luat.
4. Repetăm până se termină ambele cozi.

Este ca și cum am amesteca două pachete de cărți deja ordonate - mereu alegem cartea mai mică dintre cele două de deasupra.

Exemplu detaliat pas cu pas

a:  2  5  8  12       (n = 4)
b:  3  7  9  15  20   (m = 5)
c:  ?                  (rezultat, va avea n + m = 9 elemente)

Folosim trei indici: i pentru a, j pentru b, k pentru c.

Când un vector se termină, copiem ce a rămas din celălalt.

Codul complet

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int a[100001], b[100001], c[200001];
int n, m;

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> a[i];
    }

    fin >> m;
    for (int j = 1; j <= m; j++) {
        fin >> b[j];
    }

    int i = 1, j = 1, k = 0;

    while (i <= n && j <= m) {
        if (a[i] <= b[j]) {
            k++;
            c[k] = a[i];
            i++;
        } else {
            k++;
            c[k] = b[j];
            j++;
        }
    }

    // Copiem ce a rămas din a
    while (i <= n) {
        k++;
        c[k] = a[i];
        i++;
    }

    // Copiem ce a rămas din b
    while (j <= m) {
        k++;
        c[k] = b[j];
        j++;
    }

    // Afișăm rezultatul
    for (int p = 1; p <= k; p++) {
        fout << c[p] << " ";
    }

    return 0;
}

date.in:

4
2 5 8 12
5
3 7 9 15 20

date.out:

2 3 5 7 8 9 12 15 20

Structura algoritmului

Algoritmul are trei etape:

Etapa 1: bucla principală

while (i <= n && j <= m) {

Cât timp ambii vectori mai au elemente, comparăm și alegem pe cel mai mic.

Etapa 2: restul din a

while (i <= n) {

Dacă b s-a terminat dar a mai are elemente, le copiem pe toate.

Etapa 3: restul din b

while (j <= m) {

Dacă a s-a terminat dar b mai are elemente, le copiem pe toate.

De ce este eficientă?

Interclasarea parcurge fiecare element o singură dată. Dacă a are n elemente și b are m elemente, algoritmul face exact n + m pași.

Interclasarea este mult mai rapidă decât sortarea, pentru că profită de faptul că vectorii sunt deja sortați.

Interclasare fără vector suplimentar

Dacă nu avem nevoie de vectorul c și vrem doar să afișăm rezultatul, putem scrie direct:

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int a[100001], b[100001];
int n, m;

int main()
{
    fin >> n;
    for (int i = 1; i <= n; i++) {
        fin >> a[i];
    }

    fin >> m;
    for (int j = 1; j <= m; j++) {
        fin >> b[j];
    }

    int i = 1, j = 1;

    while (i <= n && j <= m) {
        if (a[i] <= b[j]) {
            fout << a[i] << " ";
            i++;
        } else {
            fout << b[j] << " ";
            j++;
        }
    }

    while (i <= n) {
        fout << a[i] << " ";
        i++;
    }

    while (j <= m) {
        fout << b[j] << " ";
        j++;
    }

    return 0;
}

Interclasare cu eliminarea duplicatelor

Dacă vrem ca rezultatul să conțină fiecare valoare o singură dată:

int i = 1, j = 1, k = 0;

while (i <= n && j <= m) {
    if (a[i] < b[j]) {
        k++;
        c[k] = a[i];
        i++;
    } else if (a[i] > b[j]) {
        k++;
        c[k] = b[j];
        j++;
    } else {
        // Sunt egale - luăm o singură dată
        k++;
        c[k] = a[i];
        i++;
        j++;
    }
}

while (i <= n) {
    k++;
    c[k] = a[i];
    i++;
}

while (j <= m) {
    k++;
    c[k] = b[j];
    j++;
}

Exemplu:

a:  1  3  5  7
b:  2  3  5  8

Rezultat (fără duplicate):  1  2  3  5  7  8

Când a[i] == b[j], luăm valoarea o singură dată și avansăm în ambii vectori.

Reuniunea și intersecția

Interclasarea stă la baza a două operații importante:

Reuniunea (toate elementele, fără duplicate)

Exact varianta de mai sus - luăm fiecare valoare o singură dată.

Intersecția (doar elementele comune)

Afișăm valoarea doar când a[i] == b[j]:

int i = 1, j = 1;

while (i <= n && j <= m) {
    if (a[i] < b[j]) {
        i++;
    } else if (a[i] > b[j]) {
        j++;
    } else {
        fout << a[i] << " ";
        i++;
        j++;
    }
}

Exemplu:

a:  1  3  5  7  9
b:  2  3  5  8  9

Intersecție:  3  5  9

Greșeli frecvente

1. Uitarea copierii restului

while (i <= n && j <= m) {
    // ... comparare și copiere
}
// GREȘIT: lipsesc buclele pentru restul din a și b!

Dacă un vector se termină înaintea celuilalt, elementele rămase trebuie copiate.

2. Condiția <= vs < la comparare

if (a[i] <= b[j]) {  // CORECT: elementele egale merg la a (sau b, nu contează)
if (a[i] < b[j]) {   // OK și asta, dar trebuie tratat cazul de egalitate

Cu <=, elementele egale din a vin primele. Cu <, vin cele din b. Ambele sunt corecte.

3. Vectorii nu sunt sortați

Interclasarea funcționează doar dacă ambii vectori sunt sortați. Dacă nu sunt, trebuie sortați mai întâi.

4. Vectorul c prea mic

Vectorul rezultat are n + m elemente. Dacă n și m pot fi câte 100.000, atunci c trebuie declarat cu 200.001 poziții.

Ce să reții

• Interclasarea combină doi vectori sortați într-unul singur, tot sortat.
• Parcurgem ambii vectori simultan, alegând mereu elementul mai mic.
• Când un vector se termină, copiem restul din celălalt.
• Algoritmul face exact n + m pași - foarte eficient.
• Variante utile: fără duplicat (reuniune), doar comune (intersecție).
• Funcționează doar pe vectori sortați.

Probleme

pbinfoInterclasare→

pbinfoInterclasare1→

pbinfoInterclasare2→

pbinfoInterclasare3→

pbinfoInterclasnomemory1→