Fiind dați doi vectori sortați, prin interclasarea lor se înțelege construirea unui al treilea vector sortat care să conțină toate elementele acestora. Printre cele mai importante aplicații ale interclasării se numără reuniunea și intersecția a două mulțimi, dar mai ales sortarea prin interclasare. În acest articol voi prezenta implementarea algoritmului de interclasare în C++, și de asemenea cum poate fi modificat acesta pentru a calcula reuniunea și intersecția a două mulțimi.

În continuare, vom considera că vrem să interclasăm vectorii a, de lungime m, și b, de lungime n, formând un vector c, de lungime p. Toți vectorii vor fi indexați de la 0.

Exemplu

Soluții naive

Printre primele soluții care ne vin în minte se regăsesc:

a) Copiem tot vectorul a în c, iar apoi luăm pe rând elementele lui b, și le inserăm pe pozițiile lor corespunzătoare în c. Mai precis, parcurgem de la dreapta la stânga vectorul c, cât timp elementele sale sunt mai mici decât elementul curent din b, timp în care le mutăm cu o poziție la dreapta, pentru a-i face loc elementului nou. Procedeul este similar sortării prin inserție. Complexitatea algoritmului este $O(m \cdot n)$.

b) Concatenăm cei doi vectori în c (introducem în c elementele lui a, iar în continuare elementele lui b), și apoi sortăm vectorul c. Complexitatea diferă în funcție de algoritmul de sortare ales, dar în cel mai bun caz este $O((m + n) \cdot \log_2 (m + n))$.

c) Dacă intervalul de valori este suficient de mic, putem lua un vector de frecvență în care să reținem de câte ori apare în cei doi vectori fiecare element din acel interval, și apoi să-l parcurgem inserând în c elementele corespunzătoare, similar sortării prin numărare. Timpul de rulare al algoritmului are complexitatea $O(m + n + lg)$, unde lg este lungimea intervalului.

Interclasare în $O(m + n)$

Totuși, soluțiile de mai sus nu prea se folosesc de faptul că vectorii a și b sunt deja sortați. Ei bine, privind problema recursiv, putem deduce destul de ușor algoritmul optim de interclasare: Pentru a interclasa secvențele a[i, m) și b[j, n), trebuie mai întâi să inserăm în c minimul dintre a[i] și b[j], iar apoi să interclasăm secvențele rămase. Acestea sunt a[i + 1, m) și b[j, n) în cazul în care a[i] < b[j], sau a[i, m) și b[j + 1, n) în caz contrar. Nu este nevoie să tratăm separat cazul a[i] == b[j], deoarece nu are importanță pe care îl vom insera primul în c.

Așadar, algoritmul iterativ (ce se folosește în principal de o structură repetitivă) sună astfel:

  • Reținem în i poziția curentă din a, iar în j poziția curentă din b. Inițializăm i și j cu 0. Reținem de asemenea în p lungimea curentă a lui c, care inițial este 0.
  • Parcurgem simultan cei doi vectori, cât timp i < m și j < n.
    • Dacă a[i] < b[j], atunci c[p] devine a[i], și îi incrementăm pe i și p.
    • Altfel, c[p] devine b[j], și îi incrementăm pe j și p.
  • Inserăm în c elementele rămase din a.
  • Inserăm în c elementele rămase din b.

Iată o animație făcută de mine care ilustrează modul în care lucrează acest algoritm pe vectorii din exemplu:

Mai jos puteți vedea implementarea algoritmului în C++:

Se observă că după primul while, într-un vector întotdeauna vor mai rămâne elemente de inserat în c. Prin urmare, doar unul dintre următoarele două while-uri se va executa. Complexitatea algoritmului este $O(m + n)$, deoarece fiecare element din a și b va fi folosit o singură dată.

O implementare mai elegantă

Implementarea pe care urmează să o prezint este la fel de eficientă ca cea precedentă, însă e mai drăguță și ceva mai scurtă. Ideea este să adăugăm la vectorii a și b o valoare INF, mai mare decât numărul maxim care se poate afla inițial în ei (o santinelă). Astfel, pentru primul while este suficientă condiția i < m && j < n, și nu vom mai avea nevoie de celelalte două while-uri: Când s-au terminat elementele dintr-un vector, valorile din celălalt vor fi comparate cu INF, care sigur e mai mare decât ele.

Iată mai jos o sursă C++ completă, ce cuprinde citirea, interclasarea și afișarea vectorilor. Drept INF am folosit constanta INT_MAX, din header-ul <climits>. Aceasta este egală cu cea mai mare valoare ce poate fi reținută de tipul int.

Reuniunea și intersecția a două mulțimi prin interclasare

O aplicație importantă a interclasării este efectuarea operațiilor de reuniune și intersecție a două mulțimi. În continuare, vom considera că cele două mulțimi date sunt chiar vectorii a și b, cu condiția suplimentară că fiecare dintre aceștia are toate elementele distincte două câte două. Mulțimea-rezultat se va afla în vectorul c.

Modificările pe care trebuie să i le aducem algoritmului de interclasare pentru a obține reuniunea, respectiv intersecția a două mulțimi sunt: Pentru reuniune, când a[i] == b[j], vom avansa în ambii vectori, ca să nu introducem de două ori aceeași valoare în c.

Pentru intersecție, introducem elemente în c doar atunci când a[i] == b[j], pentru că celelalte (până la pasul respectiv) nu se regăsesc în ambii vectori.

O altă aplicație importantă a interclasării este sortarea prin interclasare (Merge Sort), dar despre ea voi discuta în alt articol. Dacă aveți vreo întrebare legată de algoritmul de interclasare în C++, nu ezitați să o adresați mai jos, în rubrica de comentarii 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!