Algoritmul de Interclasare

Algoritmul presupune interclasarea a doua colectii de obiecte ordonate crescator si scrierea rezultatului intr-o a treia colectie astfel incat colectia rezultata sa fie ordonata crescator si sa contina toate elementele din cele doua colectii initiale. Daca un element apare in ambele colectii atunci va aparea de doua ori in colectia rezultata.

In exemplul de mai jos este o functie C++ care ia ca argumente doi vectori de numere intregi ordonate crescator si interclaseaza cei doi vectori intr-un al treilea care este dat ca ultim argument functiei. Functia intoarce lungimea vectorului rezultat care este intotdeauna suma lungimilor celor doi vectori initiali. Ultimul argument al functiei este folosit ca parametru de iesire.

int Interclasare(int v1[], int n1, int v2[], int n2,
            int v[])
{
    int i = 0; // index pentru v1
    int j = 0; // index pentru v2
    int k = 0; // index pentru vectorul rezultat v

    // scriu in v cel mai mic numar dintr v1[i] si v2[j] si avansez cu indexul corespunzator
    while (i < n1 && j < n2)
    {
        if (v1[i] <= v2[j])
        {
            v[k] = v1[i];
            i++;
        }
        else
        {
            v[k] = v2[j];
            j++;
        }
        k++;
    }

    if (i < n1)
    {
        // scriu in v ce a mai ramas din v1
        for (; i < n1; i++)
        {
            v[k] = v1[i];
            k++;
        }
    }
    else if (j < n2)
    {
        // scriu in v ce a mai ramas din v2
        for (; j < n2; j++)
        {
            v[k] = v2[j];
            k++;
        }
    }

    return k;
}