Modul 02 — Interclasarea · Clasa a X-a Fable

Înainte de cod: ce fac k++, ++k și v[k++]?

Codul interclasării e plin de c[k++] = .... Dacă expresia asta ți se pare o vrăjitorie, oprește-te aici — o descâlcim complet înainte de a merge mai departe.

Cele două fețe ale lui „+1"

k++ (post-incrementare)
„Folosește valoarea actuală a lui k, apoi mărește-l cu 1."
Întâi dă valoarea veche, pe urmă crește.

++k (pre-incrementare)
„Mărește k cu 1 întâi, apoi folosește noua valoare."
Crește imediat, pe urmă dă valoarea nouă.

Atenție: dacă scrii k++; sau ++k; SINGURE pe o linie, fac EXACT același lucru (k crește cu 1). Diferența apare doar când valoarea lor e folosită într-o expresie — ca la v[k++].

Deci ce face v[k++] = x?

v[k++] = x e IDENTIC cu:

1v[k] = x; // scriu la poziția k ACTUALĂ

2k = k + 1; // APOI avansez

v[++k] = x e IDENTIC cu:

1k = k + 1; // avansez ÎNTÂI

2v[k] = x; // scriu la poziția NOUĂ

De aceea interclasarea folosește k++, nu ++k: pornim cu k = 0 și vrem să umplem rezultatul de la poziția 0. c[k++] scrie la 0, 1, 2… Cu c[++k] prima scriere ar nimeri la poziția 1 — am sări peste c[0]!

🔬 Laborator: execută atribuiri pas cu pas

x =

k = 0

alege o valoare x și apasă una dintre atribuiri — urmărește unde se scrie și cum se mișcă k 👆

Nivelul următor: v[x++] = w[y++] — DOI indici deodată

La interclasare nu scrii o valoare fixă — copiezi dintr-o listă în alta: c[k++] = a[i++]. Sunt două post-incrementări pe o singură linie: „ia elementul w[y] și pune-l în v[x], apoi mută AMÂNDOI indicii".

v[x++] = w[y++] e IDENTIC cu:

1v[x] = w[y]; // copiez elementul curent

2x = x + 1; // avansez în destinație

3y = y + 1; // avansez în sursă

De ce contează: exact asta face c[k++] = a[i++] din interclasare — copiază a[i] în c[k], apoi avansează și indicele sursei (i), și pe al destinației (k). O linie ține locul a trei.

🔬 Laborator 2: v ← w cu doi indici și toate variațiile

w = sursa (fixă), v = destinația. Apasă o expresie și vezi CE se copiază și cum se mișcă x și y (post/pre, ++/--):

x =0 y =0

w (sursă, y):

v (dest., x):

apasă o expresie 👆

Toate variațiile, dintr-o privire

expresia	echivalent (în ordine)	efect
v[x++] = w[y++]	v[x]=w[y]; x++; y++	copiază, apoi AMBII avansează (cazul interclasării)
v[++x] = w[y++]	x++; v[x]=w[y]; y++	întâi avansează x (sare peste v[x] curent)
v[x++] = w[++y]	y++; v[x]=w[y]; x++	întâi avansează y (sare peste w[y] curent)
v[--x] = w[y++]	x--; v[x]=w[y]; y++	dă x înapoi cu 1 (rescrie poziția anterioară)
v[x++] = w[--y]	y--; v[x]=w[y]; x++	citește sursa de la coadă spre cap
w[y++]	folosește w[y], apoi y++	doar citire + avans (fără scriere)

Regula de aur: ++/-- pus ÎNAINTE (pre) schimbă indicele înainte de a-l folosi; pus DUPĂ (post) îl folosește întâi și îl schimbă după. La interclasare vrei mereu POST — folosești poziția curentă, apoi avansezi.

Comparație directă — aceeași secvență, două comportamente

Pornim cu k = 0 și scriem, pe rând, 10, 20, 30. Vezi cum diferă rezultatul:

cu v[k++] (corect pentru umplere de la 0)

pas	k	efect
v[k++]=10	0→1	v[0]=10
v[k++]=20	1→2	v[1]=20
v[k++]=30	2→3	v[2]=30

v = [10, 20, 30] ✔

cu v[++k] (sare peste v[0]!)

pas	k	efect
v[++k]=10	0→1	v[1]=10
v[++k]=20	1→2	v[2]=20
v[++k]=30	2→3	v[3]=30

v = [?, 10, 20, 30] — v[0] a rămas gol!

Metoda: doi indicatori, coboară mereu minimul

Compari elementele curente din A și B; cel mai mic coboară în rezultat, iar indicele lui avansează. Când o listă se termină, restul celeilalte se „toarnă" direct.

A = B =

1int i = 0, j = 0, k = 0;

2while (i < n && j < m)

3 if (a[i] <= b[j]) c[k++] = a[i++];

4 else c[k++] = b[j++];

5while (i < n) c[k++] = a[i++]; // restul din A

6while (j < m) c[k++] = b[j++]; // restul din B

i = 0j = 0k = 0

A (i):

B (j):

rezultat (k):

Apasă „Pas" — linia de cod care se execută se aprinde, iar cel mai mic element coboară în rezultat. 👆

Concept-cheie: fiecare element e atins exact o dată → O(n+m). Comparativ: să lipești listele și să le resortezi ar costa O((n+m)·log(n+m)) — mai mult, degeaba. Interclasarea e fundamentul lui Merge Sort.

Detalii care aduc puncte la BAC: ① condiția a[i] <= b[j] (cu egal!) păstrează stabilitatea — ordinea relativă a elementelor egale; ② nu uita să torni resturile — la final doar UNA dintre liste mai are elemente (cealaltă e goală); ③ folosești un singur index k pentru rezultat, pornit de la 0 (de-aia k++, nu ++k).

Două liste sortate devin una singură