Școala Româno-Britanică
Modulul 3 Clasa a X-a | C++

Ora 6: Interclasarea a două liste sortate

Ce vei învăța astăzi: Algoritmul interclasării cu trei indici, i, j și k

Rezultat practic: Implementezi interclasarea a două tablouri sortate într-un tablou rezultat, tot sortat, în C++ (Competența 3.2).

Competența 3.2 Săptămâna 14

Înainte de a începe

De ce contează? Interclasarea combină două liste sortate într-una singură, sortată, în timp liniar O(n + m) - mai rapid decât sortarea de la zero a tuturor elementelor, exact ce cer problemele de BAC cu două șiruri.

Ce știi deja?

Știi să verifici dacă o listă este sortată și aplici căutarea binară pe liste sortate (orele 4-5). Interclasarea pornește exact de la două astfel de liste sortate pentru a produce o listă rezultat - ce crezi că se întâmplă dacă una dintre liste nu este sortată?

Ideea-cheie: La fiecare pas copiem elementul mai mic dintre cele două curente; când o listă se epuizează (rămâne fără elemente), copiem direct restul celeilalte - de aceea interclasarea parcurge fiecare element o singură dată și are complexitatea O(n + m).
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei înțelege ce este interclasarea (operația de combinare a două liste sortate într-o singură listă sortată), cum folosim trei indici (variabile care arată poziția curentă în fiecare tablou) i, j și k și cum construim un tablou rezultat sortat din două tablouri sortate.

Ce este interclasarea a două liste
Algoritmul cu trei indici i, j și k
Copierea elementelor rămase
Complexitatea O(n + m)

Ce este interclasarea?

Definiție: Interclasarea este operația prin care combinăm două liste sortate într-o singură listă sortată, parcurgându-le simultan și alegând mereu elementul mai mic dintre cele două curente.

Complexitatea interclasării este O(n + m), unde n și m sunt lungimile celor două liste.

Analogia din viața reală:

Ai două pachete de cărți, fiecare sortat crescător. Vrei să le amesteci într-un singur pachet tot sortat. La fiecare pas iei cartea mai mică dintre cele două de sus, până se epuizează un pachet, apoi iei restul din celălalt.

Algoritmul cu trei indici

Folosim trei indici: i parcurge primul tablou (a), j parcurge al doilea tablou (b), iar k construiește tabloul rezultat (c). Cât timp ambele tablouri au elemente necitite, copiem elementul mai mic. La final copiem restul.

Algoritmul Interclasare(a, b, n, m): // pasul 1: inițializarea indicilor i <- 1, j <- 1, k <- 0 // pasul 2: cât timp ambele liste au elemente necitite cât timp i <= n și j <= m execută dacă a[i] <= b[j] atunci k <- k + 1 c[k] <- a[i] i <- i + 1 altfel k <- k + 1 c[k] <- b[j] j <- j + 1 sfârșit dacă sfârșit cât timp // pasul 3: copiem elementele rămase din prima listă cât timp i <= n execută k <- k + 1 c[k] <- a[i] i <- i + 1 sfârșit cât timp // pasul 4: copiem elementele rămase din a doua listă cât timp j <= m execută k <- k + 1 c[k] <- b[j] j <- j + 1 sfârșit cât timp // pasul 5: afișăm tabloul rezultat pentru i = 1, k execută scrie c[i], spațiu sfârșit pentru
Program complet: interclasarea lui a și b în c
#include <iostream>
using namespace std;

int main() {
    int n, m, a[100005], b[100005], c[200005], i, j, k;
    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;
    k = 0;
    while (i <= n && j <= m) {
        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;
}

Observă: după ce o listă se epuizează, copiem elementele rămase din cealaltă cu două bucle while separate.

Pas cu pas: interclasarea pe un exemplu

Exemplu: a = 1 3 5 și b = 2 4 6

Pașii algoritmului
i=1, j=1 a[1]=1 <= b[1]=2, copiem 1, i=2
i=2, j=1 a[2]=3 > b[1]=2, copiem 2, j=2
i=2, j=2 a[2]=3 <= b[2]=4, copiem 3, i=3
i=3, j=2 a[3]=5 > b[2]=4, copiem 4, j=3
i=3, j=3 a[3]=5 <= b[3]=6, copiem 5, i=4
i=4, j=3 a s-a epuizat, copiem restul: 6. Rezultat: 1 2 3 4 5 6

Observă: în 6 pași am obținut tabloul sortat 1 2 3 4 5 6, exact câte elemente sunt în total (n + m = 6).

Program complet: interclasare cu afișare directă
#include <iostream>
using namespace std;

int main() {
    int n, m, a[100005], b[100005], i, j;
    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]) {
            cout << a[i] << " ";
            i++;
        } else {
            cout << b[j] << " ";
            j++;
        }
    }
    while (i <= n) {
        cout << a[i] << " ";
        i++;
    }
    while (j <= m) {
        cout << b[j] << " ";
        j++;
    }
    return 0;
}

Exercițiu de completare

Completează enunțul cu cuvintele potrivite:

Interclasarea combină două tablouri ______ într-un tablou rezultat, de asemenea ______. Folosim câte un indice pentru fiecare tablou plus un indice pentru tabloul ______.

Bancă de cuvinte:
sortate sortat rezultat paralele

Exercițiu de completare 2

Completează afirmațiile despre algoritm:

Comparăm a[i] cu b[j] și îl copiem pe cel mai ______ în c[k]. Când un tablou se termină, copiem restul din celălalt tablou cu o buclă ______.

Bancă de cuvinte:
mic while mare for

Test de înțelegere

Test rapid - interclasarea:

1. Indicele k din interclasare parcurge:

2. Când a[i] <= b[j], la interclasare copiem:

3. După ce un tablou s-a epuizat, la interclasare:

Ai grijă la: uitarea celor două bucle care copiază elementele rămase din lista mai lungă: fără ele, jumătate din rezultat dispare, iar programul se compilează și rulează fără nicio eroare - greșeala se vede doar la verificarea ieșirii.

Aprofundare

De ce interclasarea este atât de eficientă? Fiecare element este copiat exact o dată și se face cel mult o comparație pe copiere. În total avem n + m copieri și aproximativ n + m comparații, deci complexitatea liniară O(n + m) (complexitate în care numărul de pași crește proporțional cu numărul de date). Compară cu sortarea unei liste cu n + m elemente, care ar costa O((n + m)^2) prin selecție: pentru două liste de 100000 de elemente fiecare, interclasarea face 200000 de pași, pe când sortarea prin selecție ar face zece miliarde de pași. Acesta este motivul pentru care interclasarea stă la baza algoritmului de sortare Merge Sort.

Cazul cu elemente egale - alegerea cu <=: atunci când a[i] == b[j], condiția a[i] <= b[j] copiază mai întâi elementul din a. Rezultatul rămâne corect oricum am alege, iar în problema clasică de interclasare (unde dublurile se păstrează) ambele valori ajung în tabloul rezultat. Regula <= este însă importantă la fuzionare, unde dublurile trebuie eliminate.

Memoria suplimentară: interclasarea are nevoie de un tablou rezultat de dimensiune n + m. Dacă problema cere doar afișarea rezultatului, putem evita tabloul c și afișa direct elementul ales la fiecare pas - variantă mai simplă, folosită des la BAC. Dacă însă rezultatul trebuie folosit mai departe (de exemplu, căutat binar), construim tabloul c.

Aplicație din viața reală: doi directori de promoție au fiecare lista elevilor unei clase, sortată alfabetic. Interclasarea celor două liste produce, într-o singură parcurgere, lista alfabetică completă a ambelor clase - exact ce face profesorul când unește două cataloage ordonate.

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Interclasare

Enunț:

Cerință: Se dau două șiruri de numere naturale, fiecare sortat crescător. Să se afișeze, în ordine crescătoare, toate elementele celor două șiruri, obținute prin interclasare.

Date de intrare:

Programul citește de la tastatură numărul n, apoi cele n valori ale primului șir, numărul m, apoi cele m valori ale celui de-al doilea șir.

Date de ieșire:

Programul va afișa cele n + m valori, în ordine crescătoare, separate prin spații.

Restricții și precizări:

1 <= n, m <= 100000, valorile sunt numere naturale.

Exemplu:

Intrare:

3
1 3 5
3
2 4 6

Ieșire:

1 2 3 4 5 6
Cum gândim soluția:
  1. Citim cele două șiruri sortate
  2. Folosim indicii i și j pentru cele două șiruri și k pentru rezultat
  3. Copiem elementul mai mic, apoi restul din șirul neepuizat
  4. Afișăm tabloul rezultat
Scrie soluția în C++:
Soluție corectă:
Soluția completă
#include <iostream>
using namespace std;

int main() {
    int n, m, a[100005], b[100005], c[200005], i, j, k;
    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;
    k = 0;
    while (i <= n && j <= m) {
        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;
}

Ce învățăm: interclasarea păstrează ordinea sortată și se termină în n + m pași, fără să sortăm din nou tabloul rezultat.

PbInfo - Elemente comune

Enunț:

Cerință: Se dau două șiruri de numere naturale, fiecare sortat crescător. Să se afișeze elementele care apar în ambele șiruri, în ordine crescătoare, fără a se repeta.

Date de intrare:

Programul citește de la tastatură numărul n, apoi cele n valori ale primului șir, numărul m, apoi cele m valori ale celui de-al doilea șir.

Date de ieșire:

Programul va afișa elementele comune, în ordine crescătoare, separate prin spații.

Restricții și precizări:

1 <= n, m <= 100000, valorile sunt numere naturale.

Exemplu:

Intrare:

4
1 2 5 7
5
2 4 5 7 9

Ieșire:

2 5 7
Cum gândim soluția:
  1. Parcurgem simultan cele două șiruri cu indicii i și j
  2. Dacă a[i] == b[j], copiem valoarea și avansăm ambii indici
  3. Dacă a[i] < b[j], avansăm doar pe i; altfel, doar pe j
  4. Afișăm valorile comune
Scrie soluția în C++:
Soluție corectă:
Soluția completă
#include <iostream>
using namespace std;

int main() {
    int n, m, a[100005], b[100005], c[100005], 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]) {
            i++;
        } else {
            j++;
        }
    }

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

Ce învățăm: căutarea elementelor comune folosește aceeași idee ca interclasarea, dar copiem doar elementele egale și avansăm ambii indici o singură dată.

EXERCIȚII PRACTICE

Exercițiul Practic: Interclasarea în practică

Sarcini de lucru

Completează următoarele sarcini pentru a-ți consolida interclasarea

Sarcina 1: Interclasează și numără elementele

Cerință: Scrie un program C++ care citește două șiruri sortate, le interclasează în tabloul c și afișează atât numărul total de elemente, cât și șirul rezultat.

Soluție pentru Sarcina 1:
#include <iostream>
using namespace std;

int main() {
    int n, m, a[100005], b[100005], c[200005], i, j, k;
    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;
    k = 0;
    while (i <= n && j <= m) {
        k++;
        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++;
    }

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

Verifică: la final k este exact n + m, deoarece fiecare element a fost copiat o singură dată.

Sarcina 2: Afișează elementele comune pe loc

Cerință: Scrie un program C++ care citește două șiruri sortate și afișează direct (fără tablou auxiliar) elementele care apar în ambele, în ordine crescătoare.

Soluție pentru Sarcina 2:
#include <iostream>
using namespace std;

int main() {
    int n, m, a[100005], b[100005], i, j;
    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]) {
            cout << a[i] << " ";
            i++;
            j++;
        } else if (a[i] < b[j]) {
            i++;
        } else {
            j++;
        }
    }
    return 0;
}

Verifică: afișăm elementul comun în momentul în care îl găsim, fără a stoca un tablou rezultat.

Scrie pe caiet - De reținut

Titlul lecției

Ora 6: Interclasarea a două liste sortate

Definiția lecției

Interclasarea este operația prin care combinăm două liste sortate într-o singură listă sortată, parcurgându-le simultan și alegând mereu elementul mai mic dintre cele două curente. Folosim trei indici: i parcurge primul tablou, j parcurge al doilea, iar k construiește tabloul rezultat. Cât timp ambele tablouri au elemente necitite, comparăm a[i] cu b[j] și copiem elementul mai mic în c[k], avansând apoi indicele corespunzător. Când o listă se epuizează, copiem restul elementelor din cealaltă listă cu două bucle while separate. Fiecare element este copiat exact o dată, deci complexitatea este liniară, O(n + m). Interclasarea stă la baza algoritmului de sortare Merge Sort și rezolvă rapid problemele în care două liste deja sortate trebuie unite.

Definiții esențiale

  • Interclasarea combină două liste sortate într-o singură listă sortată, parcurgându-le simultan.
  • Folosim trei indici: i în primul tablou, j în al doilea, k în tabloul rezultat.
  • La fiecare pas copiem elementul mai mic; la final copiem restul din lista neepuizată.
  • Complexitatea: O(n + m), unde n și m sunt lungimile listelor.

Algoritmul cheie - pseudocod

Algoritmul Interclasare(a, b, n, m): i <- 1, j <- 1, k <- 0 cât timp i <= n și j <= m execută dacă a[i] <= b[j] atunci k <- k + 1 c[k] <- a[i] i <- i + 1 altfel k <- k + 1 c[k] <- b[j] j <- j + 1 sfârșit dacă sfârșit cât timp cât timp i <= n execută k <- k + 1 c[k] <- a[i] i <- i + 1 sfârșit cât timp cât timp j <= m execută k <- k + 1 c[k] <- b[j] j <- j + 1 sfârșit cât timp

Algoritmul cheie - cod C++

Interclasarea lui a și b în c
i = 1;
j = 1;
k = 0;
while (i <= n && j <= m) {
    k++;
    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

  • Inițializarea lui k cu 1: rezultatul va începe de la poziția 2, iar la final lipsește primul element.
  • Uitarea buclelor de copiere a restului: jumătate din elemente dispar din rezultat.
  • Declararea tabloului rezultat prea mic: pentru liste cu n și m elemente, c are nevoie de n + m poziții.

Exemplu practic

Doi directori de promoție au fiecare lista elevilor clasei lor, sortată alfabetic: clasa A și clasa B. Pentru a tipări o singură listă alfabetică cu toți elevii, se interclasează cele două liste. Programul de mai jos interclasează două liste sortate de nume (reprezentate prin numere de ordine) și afișează lista completă, sortată.

Interclasarea a două liste sortate
#include <iostream>
using namespace std;

int main() {
    int n, m, a[100005], b[100005], c[200005], i, j, k;
    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; k = 0;
    while (i <= n && j <= m) {
        k++;
        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++;
    }

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

Pentru listele 1 3 5 și 2 4 6, programul afișează 1 2 3 4 5 6 - toți elevii, în ordine, fără a mai sorta nimic.

Sfaturi practice și trucuri

  • Dacă rezultatul nu se mai folosește, afișează direct elementul ales, fără tabloul c.
  • Verifică pe un exemplu mic (1 3 5 și 2 4 6) pas cu pas, pe hârtie.
  • La egalitate (a[i] == b[j]), copiază mai întâi din a - convenție standard.