Interclasarea vectorilor la BAC: algoritm C++

Interclasarea a doi vectori ordonați construiește un al treilea vector ordonat comparând mereu primele elemente încă neprelucrate. Alegi valoarea mai mică, o adaugi la rezultat și avansezi numai în vectorul din care ai luat-o. Când unul dintre vectori se termină, copiezi elementele rămase din celălalt.

Metoda este eficientă deoarece fiecare element este copiat o singură dată. La BAC, cele mai frecvente greșeli sunt avansarea ambilor indici după o singură copiere, omiterea restului unui vector și eliminarea accidentală a valorilor egale. Vom urmări toate aceste situații pe exemple originale pentru pregătirea la informatică.

Condiția de pornire: ambele surse sunt ordonate

Vom presupune că ambii vectori sunt ordonați crescător, cu egalități permise. Primul element neprelucrat al fiecărui vector este atunci cel mai mic dintre elementele rămase în acel vector.

Comparând cele două elemente curente, putem alege cel mai mic element rămas în ansamblu. Nu trebuie să cercetăm toate pozițiile viitoare. Aceasta este proprietatea care face posibilă interclasarea într-un timp liniar.

Dacă unul dintre vectori nu este ordonat, metoda nu mai garantează un rezultat ordonat. De exemplu, un element mic ascuns după unul mare nu va fi ales la momentul potrivit. Verifică această condiție în enunț înainte să alegi algoritmul.

Trei indici cu semnificații diferite

Primul indice arată elementul curent din primul vector. Al doilea arată elementul curent din al doilea vector. Al treilea arată prima poziție liberă din rezultat, adică numărul elementelor deja copiate.

La fiecare copiere, indicele rezultatului crește cu unu. Dintre indicii surselor, crește numai cel corespunzător elementului ales. Celălalt element trebuie păstrat pentru comparația următoare, deoarece nu a fost încă introdus în rezultat.

Pentru primul vector unu, patru, patru, nouă și al doilea doi, patru, șapte, lungimea rezultatului va fi șapte. Interclasarea obișnuită păstrează toate aparițiile, inclusiv cele trei valori patru existente în total.

Exemplu pas cu pas

Element curent din primul	Element curent din al doilea	Element ales	Rezultat după copiere
1	2	1 din primul	1
4	2	2 din al doilea	1, 2
4	4	4 din primul	1, 2, 4
4	4	4 din primul	1, 2, 4, 4
9	4	4 din al doilea	1, 2, 4, 4, 4
9	7	7 din al doilea	1, 2, 4, 4, 4, 7

Al doilea vector s-a terminat. Copiem apoi valoarea nouă rămasă din primul vector. Rezultatul final este unu, doi, patru, patru, patru, șapte, nouă.

La egalitate, am ales din primul vector. Puteam alege din al doilea pentru o interclasare numerică obișnuită, atât timp cât păstram și cealaltă apariție pentru un pas ulterior. Regula trebuie să fie consecventă.

Program C++ complet

Programul citește lungimile celor doi vectori, apoi elementele primului și elementele celui de-al doilea. Fiecare lungime este între zero și o mie, iar vectorii sunt deja ordonați crescător. Rezultatul are capacitate pentru suma lungimilor.

#include <iostream>
using namespace std;

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

    int i = 0, j = 0, k = 0;
    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++];
    while (j < m) c[k++] = b[j++];

    cout << k << '\n';
    for (int p = 0; p < k; ++p) {
        if (p > 0) cout << ' ';
        cout << c[p];
    }
    return 0;
}

Operatorii de incrementare postfixată folosesc valoarea curentă a indicelui, apoi îl măresc. Dacă această scriere te încurcă, o poți înlocui cu o atribuire urmată de două incrementări pe linii separate. Algoritmul nu depinde de forma compactă a instrucțiunilor.

Condiția principală cere ca ambele surse să mai aibă elemente. Folosirea unei disjuncții în locul conjuncției ar permite intrarea în buclă când una dintre surse este deja epuizată. Comparația ar putea accesa o poziție invalidă.

De ce sunt necesare cele două bucle finale

Bucla principală se oprește imediat ce una dintre surse s-a terminat. Cealaltă poate avea încă elemente. Acestea sunt deja ordonate între ele și sunt cel puțin egale cu ultimul element introdus, conform alegerilor anterioare.

Nu mai trebuie comparate cu o sursă goală. Le copiezi direct, în ordinea existentă. Dacă omiți această etapă, rezultatul poate fi ordonat, dar incomplet. Verificarea lungimii finale, care trebuie să fie suma lungimilor inițiale, descoperă imediat eroarea.

Dacă un vector este vid de la început, bucla principală nu rulează, iar bucla finală corespunzătoare copiază întreaga sursă nevidă. Dacă ambele sunt vide, lungimea rezultatului este zero și nu se afișează niciun element.

Justificarea ordinii rezultatului

Înaintea fiecărui pas, partea deja construită conține cele mai mici elemente prelucrate până atunci, în ordine crescătoare. Elementele curente sunt cele mai mici dintre cele rămase în fiecare sursă.

Alegerea minimului dintre ele adaugă exact următorul element potrivit. Nu există un element mai mic ascuns mai departe în vreuna dintre surse, deoarece fiecare sursă este ordonată. Prin repetarea acestui raționament, rezultatul rămâne ordonat și nu pierde nicio apariție.

Observă că justificarea leagă condiția inițială de fiecare alegere. Nu este suficient să spui doar „compar și copiez”. Pentru a fixa această legătură, poți aplica metoda din articolul despre memorare și înțelegere.

Egalități, reuniune și intersecție

Interclasarea obișnuită păstrează duplicatele. Dacă se cere o reuniune fără repetări, trebuie adăugată o regulă care evită introducerea aceleiași valori de mai multe ori. Nu presupune această regulă doar fiindcă vectorii au elemente comune.

Pentru o intersecție, urmărești valorile prezente în ambele surse, iar comportamentul la egalitate depinde de cerința despre multiplicități. Intersecția mulțimilor și intersecția cu păstrarea anumitor numere de apariții sunt probleme diferite.

De aceea, citește exact dacă se cere „interclasare”, „elemente distincte”, „valori comune” sau „toate aparițiile”. Aceleași două surse pot conduce la rezultate de lungimi diferite pentru aceste cerințe.

Complexitate și memorie

Fiecare pas mărește cel puțin unul dintre indicii surselor, iar fiecare element este copiat o singură dată. Timpul este proporțional cu suma lungimilor. Nu este necesară sortarea din nou a rezultatului, fiindcă ordinea este păstrată la construcție.

Programul rezervă un vector rezultat de dimensiunea maximă posibilă. Memoria pentru rezultat este proporțională cu suma lungimilor în problema generală. Dacă se cere doar afișarea, poți transmite fiecare element ales direct la ieșire, fără să memorezi vectorul rezultat.

Această variantă de afișare directă cere atenție la separatori și nu permite apoi accesarea rezultatului pentru alte calcule. Ca de obicei, structura de date se alege după toate cerințele, nu doar după prima etapă a rezolvării.

Exerciții cu răspunsuri

Interclasează unu, cinci cu doi, trei, șase. Rezultatul este unu, doi, trei, cinci, șase. După alegerea lui cinci, primul vector este epuizat și se copiază șase.

Interclasează doi, doi cu doi. Rezultatul are trei valori doi. O singură valoare doi ar reprezenta o reuniune fără repetări, nu interclasarea cerută.

Interclasează minus patru, zero cu minus trei, doi. Rezultatul este minus patru, minus trei, zero, doi. Numerele negative nu cer schimbarea regulii de comparație.

Un vector are trei elemente, iar celălalt cinci. Rezultatul interclasării obișnuite are opt elemente, indiferent câte valori sunt egale. Această verificare controlează păstrarea tuturor aparițiilor.

Întrebări frecvente

Trebuie să avansez ambii indici la egalitate?

Nu dacă ai copiat o singură apariție și vrei să le păstrezi pe toate. Avansarea ambilor ar pierde una. Poți copia ambele și avansa ambele doar într-o variantă construită explicit astfel.

Pot concatena și apoi sorta?

Poți obține un rezultat ordonat, dar ai ignora avantajul că sursele sunt deja ordonate. Interclasarea folosește direct această proprietate și are timp liniar în suma lungimilor.

Cum verific cel mai bine programul?

Testează surse de lungimi diferite, valori egale, un vector vid și situația în care toate valorile unei surse sunt mai mici. Pentru explicații pe indicii tăi, poți lucra la meditații de informatică.