Algoritm pentru interclasarea a doi vectori

Inainte de a incepe trebuie sa mentionez faptul ca acest algoritm functioneaza doar daca avem doi vectori ce au elementele stocate in ordine crescatoare (sau descrescatoare). Scopul acestui algoritm este sa creeze un al treilea vector ce contine elementele din cei doi vectori. Bine-nteles, sortate crescator/descrescator in functie de cum erau cei doi vectori sortati initial.

Haideti sa luam un mic exemplu pe care sa lucram in continuare:

O solutie care ar rezolva problema destul de rapid este sa lipim cei doi vectori. Si sa obtinem vectorul C = {3, 5, 6, 7, 1, 4, 8}; dupa aceea sortam vectorul crescator si obtinem C = {1, 3, 4, 5, 6, 7, 8}; . Insa aceasta rezolvare nu este cea mai eficienta, datorita sortarii. Dupa cum am discutat intr-un articol recent pe site, este de preferat sa evitam sortarea de fiecare data cand putem.

Algoritmul de interclasare este:

1. Declaram un vector C – gol (k = 0)
2. Cat timp se afla elemente in ambii vectori (i <= n si j <= m):
   1. Comparam elementul A_i cu B_j
   2. Incrementam k
   3. Adaugam in C, pe pozitia k, elementul cel mai mic intre A_i cu B_j
   4. Incrementam indicele corespunzator vectorului din care am facut adaugarea (incrementam i daca elementul Ai a fost mai mic, si in caz contrar, incrementam j)
3. Verificam in care dintre cei doi vectori au mai ramas elemente.
   1. Daca i <= n atunci inseamna ca mai avem elemente in vectorul A, pe care le luam in ordine si le adaugam la finalul vectorului C.
   2. Daca j <= m atunci inseamna ca mai avem elemente in vectorul B, pe care le luam in ordine si le adaugam la finalul vectorului C.
4. Algoritmul se incheie, iar vectorul C contine elementele din A si din B ordonate crescator.

Implementarea in C++:

#include    <iostream>

using namespace std;

int main()
{
    int A[100], B[100], C[200];
    int n, m, k = 0;

    cout << "Introduceti numarul de elemente corespunzator vectorului A: "; cin >> n;
    cout << "Introduceti elementele vectorului A: ";
    for(int i = 0; i < n; i++)
        cin >> A[i];

    cout << "Introduceti numarul de elemente corespunzator vectorului B: "; cin >> m;
    cout << "Introduceti elementele vectorului B: ";
    for(int i = 0; i < m; i++)
        cin >> B[i];

    int i = 0, j = 0;
    while(i < n && j < m)
    {
        if(A[i] < B[j])
        {
            C[k] = A[i];
            k++;
            i++;
        }
        else
        {
            C[k] = B[j];
            k++;
            j++;
        }
    }

    if(i <= n)
    {
        for(int p = i; p < n; p++)
        {
            C[k] = A[p];
            k++;
        }
    }
    if(j <= m)
    {
        for(int p = j; p < m; p++)
        {
            C[k] = B[p];
            k++;
        }
    }

    for(int p = 0; p < k; p++)
        cout << C[p] << " ";

    return 0;
}

• Variabila i retine indicele elementului curent din A
• Variabila j retine indicele elementului curent din B
• Variabila k memoreaza numarul total de elemente din C. Deoarece primul element din C va fi adaugat pe pozitia 0, k va fi initial zero.
• La fiecare pas comparam elementul A_i cu elementul B_j iar cel mai mic este adaugat in C, pe pozitia k
• In momentul cand am iesit din while, completam restul elementelor ramase.