fbpx

Interclasarea a doi vectori in C++

0

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:

Cei doi vectori initiali

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 Ai cu Bj
    2. Incrementam k
    3. Adaugam in C, pe pozitia k, elementul cel mai mic intre Ai cu Bj
    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 Ai cu elementul Bj iar cel mai mic este adaugat in C, pe pozitia k
  • In momentul cand am iesit din while, completam restul elementelor ramase.
Comentarii
Se incarca comentariile...

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More