Interclasarea

Interclasarea unește două șiruri deja sortate într-un singur șir sortat. Pentru $A=[1,4,7]$ și $B=[2,4,8]$, comparăm valorile curente și alegem mereu cea mai mică: 1, 2, 4, 4, 7, 8. Duplicatele se păstrează. Dacă unul dintre șiruri se termină, copiem restul celuilalt.

Interclasarea unește două șiruri deja sortate într-un singur șir sortat, fără a ordona de la zero elementele. Se folosesc doi indici, $i$ pentru primul șir și $j$ pentru al doilea, ambii pornind de la început. La fiecare pas se compară elementele curente a[i] și b[j], se alege cel mai mic, se trece în rezultat și se avansează indicele șirului din care a fost luat. Când unul dintre șiruri se termină, restul celuilalt, care este deja sortat și mai mare decât tot ce a fost scris, se copiază fără comparații. Cele două bucle finale sunt necesare, pentru că bucla principală se oprește imediat ce unul dintre șiruri s-a epuizat. Fiecare element este preluat o singură dată, deci pentru șiruri de lungimi $n$ și $m$ se fac cel mult $n+m-1$ comparații, iar timpul este proporțional cu $n+m$. Valorile egale se păstrează. Dacă la egalitate se preia elementul din primul șir (<=), interclasarea este stabilă. Interclasarea nu este același lucru cu concatenarea: după concatenarea șirurilor $1,4,7$ și $2,4,8$ se obține $1,4,7,2,4,8$, care nu este sortat.

Exemplul 1 — șiruri de lungimi egale.

#include <iostream>
using namespace std;
int main() {
    int a[] = {1, 4, 7}, b[] = {2, 4, 8};
    int i = 0, j = 0;
    while (i < 3 && j < 3) {
        if (a[i] <= b[j]) cout << a[i++] << " ";
        else cout << b[j++] << " ";
    }
    while (i < 3) cout << a[i++] << " ";
    while (j < 3) cout << b[j++] << " ";
    return 0;
}

Se afișează 1 2 4 4 7 8. Pașii sunt: $1<2$ (se preia 1), $4>2$ (se preia 2), $4\le 4$ (se preia 4 din primul șir), $7>4$ (se preia 4 din al doilea), $7<8$ (se preia 7). Acum primul șir s-a epuizat și se copiază restul celui de-al doilea, 8. Condiția <= alege la egalitate elementul din primul șir.

Exemplul 2 — șiruri de lungimi diferite. Pentru $A=(1,3)$ și $B=(2,4,6,8)$, bucla principală face 3 comparații: $1<2$ (se preia 1), $3>2$ (se preia 2), $3<4$ (se preia 3). Primul șir s-a epuizat, iar bucla pentru restul celui de-al doilea copiază 4, 6 și 8. Rezultatul este 1 2 3 4 6 8. Numărul de comparații, 3, este mai mic decât $n+m-1=5$, pentru că restul lui $B$ a fost copiat fără comparații.

Exemplul 3 — reuniunea fără duplicate. Din șirurile $(1,4,7)$ și $(2,4,8)$ se poate obține reuniunea mulțimilor lor, adică elementele distincte din ambele. Se interclasează în același fel, dar un element se scrie numai dacă este diferit de ultimul scris: după 1, 2, 4, valoarea 4 din al doilea șir este omisă, apoi urmează 7 și 8. Rezultatul este $1,2,4,7,8$, cu 5 elemente. Condiția de omitere este x != ultim, unde ultim este ultimul element scris.

Exemplul 4 — egalitate și stabilitate. Fie $A=(3,5,5)$ și $B=(5,6)$. Notăm cu indicele „A” sau „B” originea fiecărui 5. Pașii: $3\le 5$ (se preia 3), $5\le 5$ (se preia primul 5 din $A$), $5\le 5$ (se preia al doilea 5 din $A$). Acum $A$ este epuizat și se copiază restul lui $B$: 5 și 6. Rezultatul este $3,5_A,5_A,5_B,6$: cu <=, elementele egale din primul șir apar înaintea celor din al doilea. S-au făcut 3 comparații, mai puține decât $n+m-1=4$.

Nu confunda interclasarea cu concatenarea. La urmărire, marchează separat indicii i și j și notează elementele comparate. Cele două bucle finale sunt necesare: dacă lipsesc, elementele rămase într-unul dintre șiruri nu apar în rezultat. Dacă fragmentul din subiect conține doar bucla principală, rezultatul este incomplet și trebuie citit exact așa. Compară și semnul din test: cu < în loc de <= la egalitate se preia elementul din al doilea șir, deci stabilitatea se schimbă.

Exemplu în formatul examenului. Ce se afișează în urma executării secvenței de mai jos?

int a[] = {1, 5, 9}, b[] = {2, 3, 10};
int i = 0, j = 0;
while (i < 3 && j < 3) {
    if (a[i] <= b[j]) cout << a[i++] << ' ';
    else cout << b[j++] << ' ';
}

• a) 1 2 3 5 9 10
• b) 1 2 3 5 9
• c) 1 2 3 5 10
• d) 1 2 3 9 10

Răspunsul corect este b). Se compară $1\le 2$ și se afișează 1, apoi $5>2$ și se afișează 2, apoi $5>3$ și se afișează 3, apoi $5\le 10$ și se afișează 5, apoi $9\le 10$ și se afișează 9. În acest moment $i=3$, primul șir s-a epuizat, bucla se oprește, iar valoarea 10 din al doilea șir nu a mai fost afișată, pentru că secvența nu are buclele de copiere finale. Varianta a) este rezultatul interclasării complete.

Al doilea exemplu: numărul de comparații. Fie $a=(2,4,6,8)$ și $b=(1,3,5,7)$, interclasate cu bucla principală de mai sus, care testează a[i] <= b[j]. Elementele se preiau alternativ: 1 din $b$, 2 din $a$, 3, 4, 5, 6 și 7. Abia după preluarea lui 7 se epuizează $b$, deci s-au făcut 7 comparații, adică $n+m-1$. La șirurile $(1,2,3,4)$ și $(5,6,7,8)$ se fac doar 4 comparații, pentru că primul șir se epuizează înaintea oricărui element al celui de-al doilea.

Greșeli frecvente

• Greșit: interclasarea este concatenarea celor două șiruri.
  Corect: ea produce un șir sortat, comparând valorile curente.
• Greșit: bucla principală copiază singură toate elementele.
  Corect: după terminarea unuia dintre șiruri, restul celuilalt trebuie copiat separat.
• Greșit: interclasarea cere ca șirurile să aibă aceeași lungime.
  Corect: lungimile pot fi diferite; trebuie doar ca ambele șiruri să fie sortate.

Înainte și după