Interclasarea a doi vectori sortați în C++

Interclasarea combină doi vectori deja sortați într-un al treilea vector sortat. Compari elementele curente și alegi de fiecare dată minimul disponibil. Nu sortezi din nou toate valorile, ci folosești ordinea care există în fiecare sursă.

Rezultatul păstrează toate aparițiile, inclusiv duplicatele. Reuniunea a două mulțimi, unde duplicatele se elimină, este o altă cerință și necesită o regulă suplimentară.

Cum funcționează

Menținem doi indici, i și j, care indică primele valori neconsumate din surse. Cât timp ambele surse au elemente, comparăm a[i] cu b[j]. Copiem valoarea mai mică în destinație și avansăm numai în sursa aleasă. La egalitate alegem din primul vector, o convenție utilă pentru stabilitate.

Când una dintre surse se termină, cealaltă este deja sortată. Copiem restul fără alte comparații între surse. Nu continuăm să accesăm a[i] după i=n sau b[j] după j=m. Destinația are nevoie de n+m poziții, chiar dacă foarte multe valori sunt egale.

Această operație apare în merge sort, în combinarea listelor cronologice și în prelucrarea a două colecții ordonate. Precondiția este esențială: dacă o sursă este nesortată, minimul ei curent nu este neapărat minimul tuturor valorilor rămase. Un exemplu cu trei elemente poate demonstra imediat eroarea.

Exemplu urmărit pas cu pas

Pentru A=(1,4,4) și B=(2,4,8), alegem succesiv 1 din A, 2 din B, 4 din A și încă 4 din A. A s-a terminat, deci copiem 4 și 8 din B. Rezultatul este 1,2,4,4,4,8.

Programul acceptă 0 <= n,m <= 100. Dacă o sursă este goală, prima buclă nu pornește și copierea restului rezolvă cazul. Dacă ambele sunt goale, afișăm doar o linie goală. Tablourile clasice au capacitate maximă; varianta cu vector poate păstra exact aceleași capacități pentru comparație.

Implementare C++17

Varianta cu tablou clasic:

#include <iostream>
int main() {
    int n, m, a[100], b[100], c[200];
    std::cin >> n >> m;
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    for (int j = 0; j < m; ++j)
        std::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++];
    for (int p = 0; p < k; ++p)
        std::cout << c[p] << (p + 1 == k ? '\n' : ' ');
    if (k == 0)
        std::cout << '\n';
}

Varianta echivalentă cu std::vector folosește aceleași limite și aceiași indici:

#include <iostream>
#include <vector>
int main() {
    int n, m;
    std::vector<int> a(100), b(100), c(200);
    std::cin >> n >> m;
    for (int i = 0; i < n; ++i)
        std::cin >> a[i];
    for (int j = 0; j < m; ++j)
        std::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++];
    for (int p = 0; p < k; ++p)
        std::cout << c[p] << (p + 1 == k ? '\n' : ' ');
    if (k == 0)
        std::cout << '\n';
}

De ce funcționează și cât costă

La fiecare pas, destinația conține în ordine cele mai mici valori deja consumate. Următorul element minim dintre toate cele rămase trebuie să fie unul dintre cele două capete, fiindcă fiecare sursă este sortată. Alegerea lui păstrează invariantul.

Timpul este O(n+m), iar destinația ocupă O(n+m) memorie. Indicii folosesc O(1) memorie suplimentară. Numărul comparațiilor între surse este cel mult n+m-1 când ambele sunt nevide; copierea elementelor rămâne necesară.

Greșeli frecvente

Nu avansa ambii indici după o singură alegere. Nu elimina valorile egale dacă cerința cere interclasare cu multiplicități. Nu presupune că spațiul pentru rezultat este maximul dintre n și m: trebuie suma.

Exersează

Interclasează A=(1,1,5) și B=(1,3). Explică de ce rezultatul are cinci elemente.

Rezolvare explicată: Rezultatul este 1,1,1,3,5. Cele trei apariții ale lui 1 provin din poziții distincte și trebuie păstrate. Lungimea este suma lungimilor, adică 3+2.

Continuă să înveți

Sortarea vectorilor, căutarea binară și divide et impera.

Întrebări frecvente

Trebuie sortați vectorii înainte de interclasare?

Da, ordinea fiecărei surse este precondiția algoritmului. Dacă datele nu sunt deja sortate, costul sortării trebuie inclus separat în analiza soluției complete.

Ce fac atunci când valorile sunt egale?

Pentru interclasarea obișnuită păstrezi ambele apariții. Poți alege mai întâi din primul vector și vei prelua cealaltă apariție într-un pas ulterior.

De ce timpul este liniar?

Fiecare pas consumă un element dintr-o sursă și îl copiază o singură dată. În total sunt n+m elemente, iar indicii nu se întorc înapoi.

Interclasarea este același lucru cu reuniunea?

Nu. Interclasarea păstrează multiplicitățile, în timp ce reuniunea de mulțimi păstrează fiecare valoare distinctă o singură dată. Enunțul stabilește regula dorită.

Cum tratez un vector gol?

Bucla care compară sursele nu se execută. Copiezi toate elementele celeilalte surse; aceeași implementare funcționează fără un algoritm separat pentru acest caz.