Bun, hai să vorbim despre un algoritm elegant și extrem de util: INTERCLASAREA. Nu e doar despre unire (cuvânt simplu) și combinare. E despre cum îmbinăm două liste deja sortate într-una singură, păstrând ordinea. E un algoritm atât de important încât e piatra de temelie a unuia dintre cei mai eficienți algoritmi de sortare: Merge Sort.
1. Ce este Interclasarea? “Lipirea a Două Listări Telefonice”
Gândește-te la interclasare ca la unirea a două agende telefonice deja sortate alfabetic:
- Ai agenda A: Ana, Cristi, Maria
- Ai agenda B: Bogdan, Dan, Elena
- Rezultat: Ana, Bogdan, Cristi, Dan, Elena, Maria
Regula de bază: Interclasarea funcționează DOAR pe vectori SORTAȚI!
2. Cum Funcționează Algoritmul? “Compară și Alege”
Ideea principală: Compară primul element din fiecare vector, ia-l pe cel mai mic, avansează în vectorul respectiv, repetă.
Analogie cu două cozi la casă:
Ai două cozi sortate după vârstă (cea mai tânără în față):
- Coada A: 10 ani, 15 ani, 20 ani
- Coada B: 12 ani, 18 ani, 22 ani
Interclasarea: ia pe rând cei mai tineri din fiecare coadă:
10 (din A), 12 (din B), 15 (din A), 18 (din B), 20 (din A), 22 (din B)
3. Algoritmul de Interclasare de Bază
#include <iostream>
using namespace std;
int main() {
// Două vectori SORTAȚI
int A[] = {1, 3, 5, 7};
int B[] = {2, 4, 6, 8};
int nA = 4; // Dimensiunea lui A
int nB = 4; // Dimensiunea lui B
// Vectorul rezultat (are dimensiunea nA + nB)
int C[8];
int i = 0; // Index pentru A
int j = 0; // Index pentru B
int k = 0; // Index pentru C
// Interclasare: compară și alege
while(i < nA && j < nB) {
if(A[i] < B[j]) {
C[k] = A[i];
i++;
} else {
C[k] = B[j];
j++;
}
k++;
}
// Dacă au rămas elemente în A, le copiem
while(i < nA) {
C[k] = A[i];
i++;
k++;
}
// Dacă au rămas elemente în B, le copiem
while(j < nB) {
C[k] = B[j];
j++;
k++;
}
// Afișare rezultat
cout << "Vectorul A: ";
for(int i = 0; i < nA; i++) cout << A[i] << " ";
cout << "\nVectorul B: ";
for(int i = 0; i < nB; i++) cout << B[i] << " ";
cout << "\nVectorul interclasat C: ";
for(int i = 0; i < nA + nB; i++) cout << C[i] << " ";
return 0;
}Ce se întâmplă pas cu pas:
A: [1, 3, 5, 7] B: [2, 4, 6, 8] C: []
Pas 1: Compar 1 și 2 → ia 1 (A), C=[1]
Pas 2: Compar 3 și 2 → ia 2 (B), C=[1,2]
Pas 3: Compar 3 și 4 → ia 3 (A), C=[1,2,3]
Pas 4: Compar 5 și 4 → ia 4 (B), C=[1,2,3,4]
Pas 5: Compar 5 și 6 → ia 5 (A), C=[1,2,3,4,5]
Pas 6: Compar 7 și 6 → ia 6 (B), C=[1,2,3,4,5,6]
Pas 7: Compar 7 și 8 → ia 7 (A), C=[1,2,3,4,5,6,7]
Pas 8: Rămâne 8 din B → C=[1,2,3,4,5,6,7,8]4. Variante ale Algoritmului
4.1 Interclasare cu elemente duplicate
#include <iostream>
using namespace std;
int main() {
int A[] = {1, 3, 3, 5};
int B[] = {2, 3, 4, 6};
int nA = 4, nB = 4;
int C[8];
int i = 0, j = 0, k = 0;
while(i < nA && j < nB) {
if(A[i] <= B[j]) { // Folosim <= pentru duplicate
C[k] = A[i];
i++;
} else {
C[k] = B[j];
j++;
}
k++;
}
// Copiere resturi...
cout << "Cu duplicate: ";
for(int i = 0; i < 8; i++) cout << C[i] << " ";
return 0;
}4.2 Interclasare descrescătoare
#include <iostream>
using namespace std;
int main() {
int A[] = {7, 5, 3, 1}; // SORTAT descrescător
int B[] = {8, 6, 4, 2}; // SORTAT descrescător
int nA = 4, nB = 4;
int C[8];
int i = 0, j = 0, k = 0;
// Schimbăm < cu > pentru descrescător
while(i < nA && j < nB) {
if(A[i] > B[j]) { // > în loc de <
C[k] = A[i];
i++;
} else {
C[k] = B[j];
j++;
}
k++;
}
// Copiere resturi...
cout << "Descrescator: ";
for(int i = 0; i < 8; i++) cout << C[i] << " ";
return 0;
}5. Interclasare Fără Duplicate
#include <iostream>
using namespace std;
int main() {
int A[] = {1, 3, 5, 7};
int B[] = {2, 3, 4, 6};
int nA = 4, nB = 4;
int C[8];
int i = 0, j = 0, k = 0;
while(i < nA && j < nB) {
if(A[i] < B[j]) {
C[k] = A[i];
i++;
k++;
}
else if(A[i] > B[j]) {
C[k] = B[j];
j++;
k++;
}
else { // Elemente egale (duplicate)
C[k] = A[i]; // Pune o singură dată
i++;
j++;
k++;
}
}
// Copiere resturi (dar acum dimensiunea lui C poate fi mai mică)
while(i < nA) {
C[k] = A[i];
i++;
k++;
}
while(j < nB) {
C[k] = B[j];
j++;
k++;
}
cout << "Fara duplicate: ";
for(int i = 0; i < k; i++) cout << C[i] << " ";
return 0;
}6. Aplicații Practice
Aplicația 1: Unirea a doi vectori de numere pare și impare
#include <iostream>
using namespace std;
int main() {
int pare[] = {2, 4, 6, 8}; // SORTAT
int impare[] = {1, 3, 5, 7}; // SORTAT
int nPare = 4, nImpare = 4;
int rezultat[8];
int i = 0, j = 0, k = 0;
while(i < nPare && j < nImpare) {
if(pare[i] < impare[j]) {
rezultat[k] = pare[i];
i++;
} else {
rezultat[k] = impare[j];
j++;
}
k++;
}
// Copiere resturi...
cout << "Pare + impare: ";
for(int i = 0; i < 8; i++) cout << rezultat[i] << " ";
return 0;
}Aplicația 2: Interclasare cu citire de la tastatură
#include <iostream>
using namespace std;
int main() {
int A[5], B[5];
cout << "Introdu 5 numere SORTATE pentru A:\n";
for(int i = 0; i < 5; i++) {
cout << "A[" << i << "] = ";
cin >> A[i];
}
cout << "\nIntrodu 5 numere SORTATE pentru B:\n";
for(int i = 0; i < 5; i++) {
cout << "B[" << i << "] = ";
cin >> B[i];
}
int C[10];
int i = 0, j = 0, k = 0;
while(i < 5 && j < 5) {
if(A[i] < B[j]) {
C[k] = A[i];
i++;
} else {
C[k] = B[j];
j++;
}
k++;
}
while(i < 5) {
C[k] = A[i];
i++;
k++;
}
while(j < 5) {
C[k] = B[j];
j++;
k++;
}
cout << "\nRezultat interclasat: ";
for(int i = 0; i < 10; i++) cout << C[i] << " ";
return 0;
}7. Interclasarea ca Funcție
#include <iostream>
using namespace std;
void interclasare(int A[], int nA, int B[], int nB, int C[]) {
int i = 0, j = 0, k = 0;
while(i < nA && j < nB) {
if(A[i] < B[j]) {
C[k] = A[i];
i++;
} else {
C[k] = B[j];
j++;
}
k++;
}
while(i < nA) {
C[k] = A[i];
i++;
k++;
}
while(j < nB) {
C[k] = B[j];
j++;
k++;
}
}
int main() {
int A[] = {1, 4, 7, 9};
int B[] = {2, 3, 5, 8};
int C[8];
interclasare(A, 4, B, 4, C);
cout << "Rezultat: ";
for(int i = 0; i < 8; i++) cout << C[i] << " ";
return 0;
}8. Complexitatea Algoritmului
#include <iostream>
using namespace std;
int main() {
cout << "=== COMPLEXITATE INTERCLASARE ===\n\n";
cout << "Dacă A are n elemente și B are m elemente:\n";
cout << "• Parcurgem fiecare element o singură dată\n";
cout << "• Facem n + m comparații\n";
cout << "• Complexitate: O(n + m)\n\n";
cout << "EXEMPLU:\n";
cout << "• A are 1000 elemente\n";
cout << "• B are 2000 elemente\n";
cout << "• Interclasarea va face cel mult 3000 de pași\n";
cout << "• Mult mai eficient decât sortarea de la zero!\n";
return 0;
}9. Merge Sort – Folosind Interclasarea
Merge Sort = împarte vectorul în jumătăți, sortează fiecare jumătate, apoi le interclasează.
#include <iostream>
using namespace std;
void interclasare(int v[], int stanga, int mijloc, int dreapta) {
int n1 = mijloc - stanga + 1;
int n2 = dreapta - mijloc;
int L[n1], R[n2];
// Copiere în vectori temporari
for(int i = 0; i < n1; i++) L[i] = v[stanga + i];
for(int j = 0; j < n2; j++) R[j] = v[mijloc + 1 + j];
// Interclasare
int i = 0, j = 0, k = stanga;
while(i < n1 && j < n2) {
if(L[i] <= R[j]) {
v[k] = L[i];
i++;
} else {
v[k] = R[j];
j++;
}
k++;
}
while(i < n1) {
v[k] = L[i];
i++;
k++;
}
while(j < n2) {
v[k] = R[j];
j++;
k++;
}
}
void mergeSort(int v[], int stanga, int dreapta) {
if(stanga < dreapta) {
int mijloc = stanga + (dreapta - stanga) / 2;
// Sortează cele două jumătăți
mergeSort(v, stanga, mijloc);
mergeSort(v, mijloc + 1, dreapta);
// Interclasează jumătățile sortate
interclasare(v, stanga, mijloc, dreapta);
}
}
int main() {
int v[] = {5, 2, 8, 1, 3, 7, 4, 6};
int n = 8;
mergeSort(v, 0, n-1);
cout << "Sortat cu Merge Sort: ";
for(int i = 0; i < n; i++) cout << v[i] << " ";
return 0;
}10. Exerciții Practice
Exercițiul 1: Completează algoritmul
int A[] = {1, 4, 6};
int B[] = {2, 3, 5};
int C[6];
int i = 0, j = 0, k = 0;
while(i < 3 && j < 3) {
if(A[i] < B[j]) {
C[k] = A[i];
/* completează */
} else {
C[k] = B[j];
/* completează */
}
k++;
}Soluție:
C[k] = A[i];
i++;
C[k] = B[j];
j++;Exercițiul 2: Ce face acest cod?
int i = 0, j = 0, k = 0;
while(i < nA && j < nB) {
if(A[i] <= B[j]) {
C[k++] = A[i++];
} else {
C[k++] = B[j++];
}
}Răspuns: Este algoritmul de interclasare (versiune compactă).
Exercițiul 3: Interclasare cu verificare dacă vectorii sunt sortați
#include <iostream>
using namespace std;
bool esteSortat(int v[], int n) {
for(int i = 0; i < n-1; i++) {
if(v[i] > v[i+1]) return false;
}
return true;
}
int main() {
int A[] = {5, 3, 1}; // NU e sortat!
int B[] = {2, 4, 6};
if(!esteSortat(A, 3) || !esteSortat(B, 3)) {
cout << "EROARE: Vectorii trebuie sa fie sortati!" << endl;
return 1;
}
// Continuă cu interclasarea...
return 0;
}Schema Universală de Interclasare:
1. i = 0 (index pentru A), j = 0 (index pentru B), k = 0 (index pentru C)
2. Cât timp i < nA și j < nB:
- Dacă A[i] < B[j]: C[k] = A[i], i++
- Altfel: C[k] = B[j], j++
- k++
3. Copiază restul din A (dacă există)
4. Copiază restul din B (dacă există)În concluzie:
- Interclasarea funcționează DOAR pe vectori SORTAȚI
- Complexitatea e O(n + m) – extrem de eficientă
- Merge Sort se bazează pe interclasare
- Regula de aur: Compară, alege, avansează în vectorul ales
Când folosești interclasarea?
- Când ai două liste sortate și vrei să le unesti păstrând ordinea
- În Merge Sort pentru a combina jumătățile sortate
- În baze de date pentru a uni rezultate sortate
- În sisteme de fișiere pentru a interclasa fișiere sortate
Leave a Reply