Scrie pe caiet - De reținut

Titlul lecției

Ora 7: Interclasarea - aplicații

Definiția lecției

Fuzionarea este interclasarea care elimină dublurile: atunci când a[i] == b[j], copiem valoarea o singură dată în tabloul rezultat și avansăm ambii indici, i și j. Când a[i] < b[j], copiem din primul tablou, iar altfel copiem din al doilea; la final, copiem restul elementelor din lista rămasă. O listă este sortată crescător dacă fiecare element este mai mic sau egal cu următorul, adică a[i] <= a[i + 1] pentru orice i de la 1 la n - 1. Verificarea sortării se face într-o singură parcurgere și are complexitatea O(n). Atât interclasarea, cât și fuzionarea au complexitatea O(n + m). Alegerea dintre cele două se face după enunț: „elementele celor două șiruri" înseamnă interclasare, iar „elementele distincte" înseamnă fuzionare.

Definiții esențiale

• Fuzionarea este interclasarea care elimină dublurile: când a[i] == b[j], copiem valoarea o singură dată și avansăm ambii indici.
• O listă este sortată crescător dacă a[i] <= a[i + 1] pentru orice i de la 1 la n - 1.
• Verificarea sortării are complexitatea O(n) - o singură parcurgere.
• Interclasarea și fuzionarea au complexitatea O(n + m).

Algoritmul cheie - pseudocod

Algoritmul cheie - cod C++

i = 1;
j = 1;
k = 0;
while (i <= n && j <= m) {
    k++;
    if (a[i] == b[j]) {
        c[k] = a[i];
        i++;
        j++;
    } else if (a[i] < b[j]) {
        c[k] = a[i];
        i++;
    } else {
        c[k] = b[j];
        j++;
    }
}
while (i <= n) {
    k++;
    c[k] = a[i];
    i++;
}
while (j <= m) {
    k++;
    c[k] = b[j];
    j++;
}

Greșeli comune de evitare

• Tratarea fuzionării ca interclasare: la egalitate, valoarea ar apărea de două ori în rezultat.
• Verificarea sortării în O(n^2): inutil; o singură parcurgere este suficientă.
• Uitarea avansării ambilor indici la egalitate: provoacă buclă infinită.

Exemplu practic

Două cluburi de lectură publică fiecare lista membrilor, sortată alfabetic. Pentru a tipări lista completă a membrilor unici (o persoană care este în ambele cluburi apare o singură dată), se folosește fuzionarea. Programul de mai jos interclasează două liste sortate de numere de ordine, eliminând dublurile.

#include <iostream>
using namespace std;

int main() {
    int n, m, a[100005], b[100005], c[200005], i, j, k = 0;
    cin >> n;
    for (i = 1; i <= n; i++)
        cin >> a[i];
    cin >> m;
    for (j = 1; j <= m; j++)
        cin >> b[j];

    i = 1; j = 1;
    while (i <= n && j <= m) {
        if (a[i] == b[j]) {
            k++;
            c[k] = a[i];
            i++;
            j++;
        } else if (a[i] < b[j]) {
            k++;
            c[k] = a[i];
            i++;
        } else {
            k++;
            c[k] = b[j];
            j++;
        }
    }
    while (i <= n) {
        k++;
        c[k] = a[i];
        i++;
    }
    while (j <= m) {
        k++;
        c[k] = b[j];
        j++;
    }

    for (i = 1; i <= k; i++)
        cout << c[i] << " ";
    return 0;
}

Pentru listele 1 2 4 și 2 3 4, programul afișează 1 2 3 4 - valoarea 2, prezentă în ambele liste, apare o singură dată.

Sfaturi practice și trucuri

• Dacă se cere doar numărul de valori distincte, numără cu k fără a construi tabloul c.
• O listă cu un singur element este întotdeauna sortată - tratează cazul limită.
• Citește enunțul: „elementele celor două șiruri" = interclasare, „elementele distincte" = fuzionare.