Se dau doi vectori cu numere naturale ordonate crescător. Se dorește formarea unui alt vector care să conțină valorile din ambii vectori, tot în ordine crescătoare.

Exemplu. Dacă avem vectorii a = (1, 2, 5, 9) și b = (3, 4, 5, 7), atunci vectorul rezultat este c = (1, 2, 3, 4, 5, 5, 7, 9).

O metodă ar fi să lipim al doilea vector de primul, după care să sortăm elementele. Deși această soluție funcționează, rezolvarea problemei devine mai complicată. În plus, nu se folosește deloc de faptul că vectorii sunt inițial sortați crescător.

În această lecție învățăm metoda eficientă de rezolvare a acestei probleme, cu ajutorul interclasării.

Algoritmul pentru interclasarea a doi vectori

Interclasarea a doi vectori constă în parcurgerea concomitentă a vectorilor, selectând pe rând elementul mai mic dintre elementul curent din primul vector și din al doilea. Iată o animație care demonstrează această idee:

Explicarea algoritmului de interclasare

Să zicem că avem cei doi vectori ordonați crescător:

• a, de lungime n;
• b, de lungime m;

Vom crea un al treilea vector, c, de lungime k, care să rețină la final interclasarea.

• Inițial, vectorul c este gol (k = 0);
• Parcurgem vectorii a și b concomitent, cu un i și un j; cu alte cuvinte, cât timp i <= n && j <= m (cât timp suntem în ambii vectori):
  • Comparăm a[i] cu b[j] (elementele curente din cei doi vectori);
  • Adăugăm elementul mai mic la c; dacă a[i] < b[j]:
    • Adăugăm la c elementul a[i] (k++, c[k] = a[i]);
    • Creștem i cu 1 (i++);
  • În caz contrar, dacă b[j] ≤ a[i]:
    • Adăugăm la c elementul b[j] (k++, c[k] = b[j]);
    • Creștem j cu 1 (j++);
• Verificăm dacă în vreunul dintre vectori au rămas elemente nepuse;
  • Dacă i <= n atunci mai avem elemente în vectorul a, pe care le adăugăm în c, pe rând;
  • Dacă j <= m atunci mai avem elemente în vectorul b, pe care le adăugăm în c, pe rând;
• Vectorul c este format.

Implementarea în C++

#include <iostream>

using namespace std;

//Declarăm cei trei vectori
int a[101], b[101], c[201], n, m, k; //Vectorul c trebuie să aibă lungimea dublă, ca să încapă elementele din ambele mulțimi

int main()
{
    //Citim vectorii a și b
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    for(int i = 1; i <= m; i++)
        cin >> b[i];

    //Începem interclasarea
    int i = 1, j = 1;
    while(i <= n && j <= m) { //Comparăm elementele a[i] și b[j] din vector
        //Luăm mereu elementul mai mic
        if(a[i] < b[j]) {
            k++;
            c[k] = a[i];
            i++;
        } else {
            k++;
            c[k] = b[j];
            j++;
        }
    }

    while(i <= n) { //Dacă intrăm în acest while, atunci vectorul b s-a epuizat, dar au rămas elemente în vectorul a, pe care le adăugăm pe rând ca mai sus
        k++;
        c[k] = a[i];
        i++;
    }

    while(j <= m) { //Dacă intrăm în acest while, atunci vectorul a s-a epuizat, dar au rămas elemente în vectorul b, pe care le adăugăm pe rând ca mai sus
        k++;
        c[k] = b[j];
        j++;
    }

    //Afișăm vectorul final
    for(int i = 1; i <= k; i++)
        cout << c[i] << " ";
    return 0;
}

Aplicații cu interclasarea a doi vectori

Reuniunea a două mulțimi prin interclasare

Dându-se doi vectori ordonați crescător reprezentând două mulțimi, să se afișeze mulțimea ce reprezință reuniunea lor. Testează-ți rezolvarea pe această pagină.

Exemplu: Pentru mulțimile a = (1, 2, 3, 4) și b = (3, 5, 6), avem reuniunea lor c = (1, 2, 3, 4, 5, 6).

Rezolvare: Să notăm cei doi vectori a și b, iar cel răspuns c. Observăm că dacă făceam interclasarea vectorilor folosind algoritmul clasic, obțineam un vector cu toate elementele din ambii, în ordine crescătoare (în exemplul de mai sus, interclasarea clasică ar fi fost c = (1, 2, 3, 3, 4, 5, 6)). Fiind vorba de mulțimi, toate elementele vectorului răspuns trebuie să fie distincte — mai precis, singura diferență pe care trebuie să o facem față de algoritmul clasic este să ne asigurăm că nu băgăm niciodată două elemente egale unul după altul.

Implementare în C++

//Reuniunea a două mulțimi
#include <iostream>

using namespace std;

//Declarăm cei trei vectori
int a[101], b[101], c[201], n, m, k;

int main()
{
    //Citim vectorii a și b
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    for(int i = 1; i <= n; i++)
        cin >> b[i];

    //Interclasarea
    int i = 1, j = 1;
    while(i <= n && j <= m) {
        if(a[i] == b[j]) { //Nu băgăm ambele elemente, ci doar pe unul dintre ele
            k++;
            c[k] = a[i]; //sau b[j]
            i++;
            j++;
        } else if(a[i] < b[j]) {
            k++;
            c[k] = a[i];
            i++;
        } else {
            k++;
            c[k] = b[j];
            j++;
        }
    }

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

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

    for(int i = 1; i <= k; i++)
        cout << c[i] << " ";
    return 0;
}

Intersecția a două mulțimi prin interclasare

Dându-se doi vectori ordonați crescător reprezentând două mulțimi, să se afișeze mulțimea ce reprezință intersecția lor. Testează-ți rezolvarea pe această pagină.

Exemplu: Pentru mulțimile a = (1, 2, 3, 4, 5) și b = (3, 5, 6), avem intersecția lor c = (3, 5).

Rezolvare: Intersecția a două mulțimi este similar cu algoritmul pentru reuniune:

• dacă întâlnim elemente egale în cele două mulțimi, adăugăm unul dintre ele în mulțimea c;
• dacă elementul curent din primul vector este mai mic decât cel din al doilea vector, trecem la următorul element din primul vector;
• dacă elementul curent din al doilea vector este mai mic decât cel din primul vector, trecem la următorul element din al doilea vector;
• la final, dacă se termină unul dintre vectori, nu mai trebuie să iterăm printre elementele sale, deoarece nu sunt egale cu niciunul din elementele celui de al doilea vector.

Implementare în C++

//Intersecția a două mulțimi
#include <iostream>

using namespace std;

//Declarăm cei trei vectori
int a[101], b[101], c[201], n, m, k;

int main()
{
    //Citim vectorii a și b
    cin >> n;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    for(int i = 1; i <= n; i++)
        cin >> b[i];

    //Interclasarea
    int i = 1, j = 1;
    while(i <= n && j <= m) {
        if(a[i] == b[j]) {
            k++;
            c[k] = a[i]; //sau b[j]
            i++;
            j++;
        } else if(a[i] < b[j]) {
            i++;
        } else {
            j++;
        }
    }

    for(int i = 1; i <= k; i++)
        cout << c[i] << " ";
    return 0;
}

Probleme propuse

Setul de probleme 144 nu a fost găsit.

Alte resurse sau bibliografie

• PbInfo: Interclasarea tablourilor unidimensionale
• InfoGenius: Interclasare
• UAIC: Interclasarea a doi vectori