Interclasare — AlgoClar

De ce contează?

Două teancuri de fișe, fiecare deja ordonat alfabetic. Vrei un singur teanc ordonat. Compari fișele de deasupra ambelor teancuri, o iei pe cea mai mică, și repeți. Fiindcă fiecare teanc e deja sortat, nu trebuie să le amesteci pe toate — doar să compari vârfurile.

Ce este interclasarea

Interclasarea combină doi vectori sortați într-unul singur, tot sortat. Cheia: amândoi fiind ordonați, la fiecare pas cel mai mic element nou e mereu la unul dintre cele două „capete" curente.

Algoritm pas cu pas

a = {1, 4, 7}, b = {2, 3, 8}. Doi indici i, j pornesc de la 0:

i	j	a[i] vs b[j]	luăm	rezultat
0	0	1 < 2	1	1
1	0	4 > 2	2	1 2
1	1	4 > 3	3	1 2 3
1	2	4 < 8	4	1 2 3 4
2	2	7 < 8	7	1 2 3 4 7
3	2	a epuizat	8	1 2 3 4 7 8

rez

Rezultatul interclasării lui {1,4,7} cu {2,3,8}: un singur vector sortat, construit luând mereu cel mai mic dintre capete.

Implementare C++

#include <iostream>
using namespace std;

int main() {
    int a[] = {1, 4, 7}, n = 3;
    int b[] = {2, 3, 8}, m = 3;
    int rez[100], k = 0;

    int i = 0, j = 0;
    while (i < n && j < m) {
        if (a[i] <= b[j]) rez[k++] = a[i++];   // luam din a
        else              rez[k++] = b[j++];   // luam din b
    }
    while (i < n) rez[k++] = a[i++];           // ce a ramas din a
    while (j < m) rez[k++] = b[j++];           // ce a ramas din b

    for (int t = 0; t < k; t++) cout << rez[t] << " ";   // 1 2 3 4 7 8
    return 0;
}

Observația-cheie

Cele două bucle while de la final sunt esențiale: când una dintre liste se termină, cealaltă mai are elemente (deja sortate și mai mari). Le copiezi direct. Fără ele, pierzi „coada" listei mai lungi.

De ce nu „concatenez și sortez"

Ai putea lipi vectorii și apela std::sort — dar asta e O((n+m) log(n+m)) și ignoră faptul că erau deja sortați. Interclasarea e O(n+m), liniară. E și nucleul algoritmului Merge Sort.

Complexitate

Metodă	Timp	Spațiu
interclasare	O(n + m)	O(n + m)
concatenare + sortare	O((n+m) log(n+m))	O(n + m)

Greșeli frecvente

Capcane reale la interclasare:

Uiți cozile: dacă nu copiezi restul listei rămase după prima buclă, pierzi elemente.
Vectori nesortați: metoda presupune ambele sortate. Pe date nesortate, rezultatul nu e ordonat.
< în loc de <=: la valori egale, <= păstrează stabilitatea (ordinea relativă); cu < tot iese sortat, dar pierzi stabilitatea — contează la elemente cu informații atașate.
Depășești rez: dimensioneaz-o la cel puțin n + m, altfel scrii în afara vectorului.

Vizualizare

Urmărește cum cei doi indici avansează și cum se alege la fiecare pas cel mai mic dintre capete:

Indiciu

Folosește ← → ca să pășești manual. Observă că doar unul dintre indici avansează la fiecare pas — cel de la care ai luat elementul mai mic.

De reținut

Interclasezi doi vectori sortați luând mereu cel mai mic dintre cele două capete.
După ce o listă se epuizează, copiezi direct coada celeilalte (deja sortată).
O(n + m), liniar — nucleul lui Merge Sort; nu concatena și sorta.