Interclasarea a doi vectori sortați

Interclasarea înseamnă combinarea a doi vectori deja sortați într-un singur vector sortat, într-o singură parcurgere. La BAC informatică apare des la problema cu date din fișier de la Subiectul III, unde primești două șiruri ordonate și ți se cere un rezultat ordonat, „eficient din punctul de vedere al timpului de executare”. Varianta „le pun pe toate într-un vector și sortez” e corectă, dar nu e cea eficientă. Aici vezi algoritmul liniar, variantele lui și cum îl scrii în C++ fără să pierzi elemente la final.

Ideea: doi indici care avansează

Ai vectorul a cu n elemente și vectorul b cu m elemente, ambele crescătoare. Ții un indice i în a și un indice j în b, amândoi la început. La fiecare pas compari a[i] cu b[j], îl copiezi pe cel mai mic în rezultat și avansezi doar în vectorul din care l-ai luat. Când unul dintre vectori se termină, copiezi tot ce a rămas din celălalt — e deja sortat și toate valorile lui sunt mai mari sau egale cu ce ai pus până atunci.

Exemplu: a = 1 4 7 9 și b = 2 4 5 10 12.

Rezultatul are n + m = 9 elemente. Fiecare element a fost copiat exact o dată, deci algoritmul face O(n + m) operații.

Codul C++

#include <iostream>
using namespace std;

int a[101], b[101], c[202];

int main()
{
    int n, m, k = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> m;
    for (int j = 1; j <= m; j++) cin >> b[j];

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

    while (i <= n) c[++k] = a[i++];     // ce a rămas în a
    while (j <= m) c[++k] = b[j++];     // ce a rămas în b

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

Instrucțiunea c[++k] = a[i++]; face trei lucruri: crește k, copiază a[i] pe poziția nouă k din c, apoi crește i. Dacă îți e mai clar, o poți scrie pe trei rânduri: k++; c[k] = a[i]; i++;.

Ultimele două bucle while sunt partea pe care o uită cei mai mulți elevi. Doar una dintre ele se execută efectiv (vectorul care nu s-a terminat), dar e mai simplu și mai sigur să le scrii pe amândouă decât să testezi care a rămas.

Dimensiunea lui c trebuie să fie cel puțin n + m (aici 202, pentru că n, m ≤ 100 și numerotăm de la 1).

Varianta fără duplicate (reuniune)

Dacă fiecare vector e strict crescător și vrei valorile din oricare dintre ei, dar fiecare o singură dată, tratezi separat cazul egalității: copiezi valoarea o dată și avansezi în ambii vectori.

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

Restul codului (copierea elementelor rămase) rămâne la fel. Pentru vectorii 1 4 7 9 și 2 4 5 10 12 se obține 1 2 4 5 7 9 10 12 — 8 valori. Dacă păstrezi doar ramura de egalitate și ignori elementele rămase, obții intersecția: aici, doar 4.

Interclasare cu date din fișier, cu memorie redusă

Fișierul bac.txt conține pe prima linie numerele n și m, pe a doua linie n numere naturale ordonate crescător, iar pe a treia m numere naturale ordonate crescător (n ≤ 10⁵, m ≤ 10⁶). Afișați pe ecran toate cele n + m numere, în ordine crescătoare, folosind un algoritm eficient.

Nu e nevoie să memorezi ambele șiruri. Păstrezi primul șir într-un vector, iar pe al doilea îl citești număr cu număr. Pentru fiecare x citit, afișezi întâi toate elementele din primul șir care sunt mai mici sau egale cu x și încă neafișate, apoi pe x.

#include <fstream>
#include <iostream>
using namespace std;

int a[100001];

int main()
{
    ifstream fin("bac.txt");
    int n, m, x;
    fin >> n >> m;
    for (int i = 1; i <= n; i++) fin >> a[i];

    int i = 1;
    for (int j = 1; j <= m; j++)
    {
        fin >> x;
        while (i <= n && a[i] <= x)
            cout << a[i++] << " ";
        cout << x << " ";
    }
    while (i <= n) cout << a[i++] << " ";
    return 0;
}

Deși are un while în interiorul unui for, algoritmul e tot liniar: indicele i doar crește, deci în total bucla interioară face cel mult n pași pe toată durata programului. Descrierea pentru punctul a) poate fi: „Se memorează primul șir; termenii celui de-al doilea șir se citesc pe rând și, înaintea fiecăruia, se afișează termenii neafișați din primul șir care sunt mai mici sau egali cu el (interclasare). Algoritmul este liniar, O(n + m), și memorează doar primul șir.”

De ce nu sortare? Să pui toate valorile într-un vector și să le sortezi face cel puțin în jur de (n + m)·log(n + m) operații cu un algoritm bun, iar cu metodele elementare (bule, selecție) ajungi la ordinul (n + m)². Interclasarea folosește faptul că datele sunt deja ordonate — exact informația pe care ți-o dă enunțul.