Clasa X - Ora 3: Sortarea prin interclasare (merge sort)

SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei înțelege principiul sortării prin interclasare: împărțim vectorul în două jumătăți, sortăm fiecare jumătate recursiv (repetând operația pe jumătăți tot mai mici) și apoi interclasăm cele două jumătăți sortate.

Ideea divizării până la un singur element

Interclasarea a două secvențe sortate

Implementarea completă în C++

Complexitatea O(n log n)

Ideea metodei

Definiție: Sortarea prin interclasare (merge sort) descompune vectorul în două jumătăți aproximativ egale, sortează fiecare jumătate prin apel recursiv, apoi interclasează cele două jumătăți sortate, obținând un vector complet sortat. Un vector cu un singur element este deja sortat (cazul de bază).

Analogie: îmbinarea a două grămezi de cartonașe ordonate

Ai două grămezi de cartonașe, fiecare ordonată crescător. Le îmbini ținând câte un deget la începutul fiecărei grămezi: compari cele două cartonașe, îl iei pe cel mai mic și înaintezi degetul din grămada respectivă. Repetând, obții o singură grămadă ordonată.

Divizare: vectorul se împarte la jumătăți până la un element
Rezolvare: un singur element este deja sortat
Combinare: interclasăm cele două jumătăți sortate

Exemplu: interclasarea a două secvențe

Secvențele sortate [1, 3, 5] și [2, 4] se interclasează astfel: comparăm 1 cu 2 (luăm 1), 3 cu 2 (luăm 2), 3 cu 4 (luăm 3), 5 cu 4 (luăm 4), apoi rămâne 5. Rezultatul: [1, 2, 3, 4, 5].

Funcția de interclasare

Funcția interclaseaza(st, mij, dr) folosește doi indici (i pentru prima jumătate, j pentru a doua) și un vector auxiliar temp. La fiecare pas copiem elementul mai mic, apoi copiem elementele rămase.

interclasarea secvențelor [1, 3, 5] și [2, 4]

i și j parcurg secvențele

i=1 v[i]=1 < v[j]=2, copiem 1, i devine 2

j=2 v[i]=3 > v[j]=2, copiem 2, j devine 5

i=3 v[i]=3 < v[j]=4, copiem 3, i devine 4

j=4 v[i]=5 > v[j]=4, copiem 4, j depășește capătul

i=5 copiem elementele rămase din prima jumătate: 5

Observă: după ce o secvență se epuizează, copiem direct elementele rămase din cealaltă. Rezultatul este întotdeauna o secvență sortată.

Programul complet: merge sort

citește n, v[1..n] mergeSort(1, n) scrie v[1..n] procedură interclaseaza(st, mij, dr): i = st, j = mij + 1, k = st cât timp i <= mij și j <= dr execută dacă v[i] < v[j] atunci temp[k++] = v[i++] altfel temp[k++] = v[j++] sfârșit cât timp cât timp i <= mij execută temp[k++] = v[i++] // copiem restul din stânga cât timp j <= dr execută temp[k++] = v[j++] // copiem restul din dreapta pentru p = st, dr execută v[p] = temp[p] // copiem înapoi sfârșit procedură procedură mergeSort(st, dr): dacă st < dr atunci mij = (st + dr) / 2 mergeSort(st, mij) // rezolvăm jumătatea stângă mergeSort(mij + 1, dr) // rezolvăm jumătatea dreaptă interclaseaza(st, mij, dr) // combinare sfârșit dacă sfârșit procedură

C++ - sortare prin interclasare

#include <iostream>
using namespace std;

int v[1001], temp[1001];

void interclaseaza(int st, int mij, int dr) {
    int i = st, j = mij + 1, k = st;
    while (i <= mij && j <= dr) {
        if (v[i] < v[j]) {
            temp[k++] = v[i++];
        } else {
            temp[k++] = v[j++];
        }
    }
    while (i <= mij) {
        temp[k++] = v[i++];
    }
    while (j <= dr) {
        temp[k++] = v[j++];
    }
    for (int p = st; p <= dr; p++) {
        v[p] = temp[p];
    }
}

void mergeSort(int st, int dr) {
    if (st < dr) {
        int mij = (st + dr) / 2;
        mergeSort(st, mij);
        mergeSort(mij + 1, dr);
        interclaseaza(st, mij, dr);
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    mergeSort(1, n);
    for (int i = 1; i <= n; i++) {
        cout << v[i] << " ";
    }
    return 0;
}

Ce învățăm: funcțiile se definesc înainte de main(); temp este vector auxiliar global; cazul de bază este st == dr (un element, deja sortat).

Exercițiu de completare

Completează descrierea sortării prin interclasare:

Sortarea prin interclasare împarte vectorul în două ______; sortează fiecare jumătate prin ______; apoi ______ cele două secvențe, obținând un vector ______.

Bancă de cuvinte:

jumătăți recursivitate interclasează sortat

Exercițiu de completare: codul interclasării

Completează descrierea funcției de interclasare:

În funcția de interclasare: indicele i pornește din st, iar j din mij + ______; copiem în ______ elementul mai ______ dintre v[i] și v[j].

Bancă de cuvinte:

1 temp mic

Test de înțelegere

Test rapid - merge sort:

1. Un vector cu un singur element este considerat:

deja sortat nesortat gol

2. Interclasarea a două secvențe sortate are complexitatea:

O(n) O(n) O(1)

3. Complexitatea totală a sortării prin interclasare este:

O(n log n) O(n) O(log n)

Ai grijă la: după interclasare, vectorul temp trebuie copiat înapoi în v pe tot intervalul [st, dr]; fără această copiere, sortarea „se pierde" între apelurile recursive.

Aprofundare

De ce interclasarea este liniară: fiecare element este comparat de cel mult o dată pe fiecare nivel al recursivității, iar numărul de niveluri este log₂(n). De aici rezultă complexitatea totală O(n log n), cu mult mai bună decât sortarea prin selecție sau inserție, de complexitate O(n).

Stabilitatea algoritmului: interclasarea compară cu < și copiază mai întâi elementul din jumătatea stângă la egalitate, deci elementele egale își păstrează ordinea relativă. Un algoritm cu această proprietate se numește stabil, ceea ce contează la sortarea după mai multe criterii (de exemplu, mai întâi după medie, apoi după nume).

Memoria suplimentară: merge sort folosește un vector auxiliar temp de aceeași dimensiune cu v, deci complexitatea de spațiu este O(n). Sortarea clasică prin selecție sortează „în loc" (in-place), dar plătește cu timp O(n); este compromisul clasic timp-memorie.

Interclasarea fără vector auxiliar: există variante care interclasează prin rotații de subsecvențe, dar sunt mult mai complicate. La Bacalaureat se folosește întotdeauna vectorul auxiliar temp, urmat de copierea înapoi în v.

Exemplu din viața reală: o firmă de curierat primește dimineața 1000 de colete cu adrese, deja sortate alfabetic pe fiecare cartier. Pentru a obține lista completă, angajații interclasează două câte două listele vecine, exact ca în pasul de combinare al merge sort. Interclasarea a două liste deja sortate se face într-o singură trecere.

APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Sortare (merge sort)

Enunț:

Cerință: Se citește un număr natural n și apoi n numere întregi. Să se afișeze numerele în ordine crescătoare, folosind sortarea prin interclasare.

Date de intrare:

Programul citește de la tastatură numărul n, apoi cele n numere.

Date de ieșire:

Programul va afișa pe ecran numerele sortate crescător, separate prin spații.

Restricții și precizări:

1 ≤ n ≤ 1000; elementele sunt numere întregi; se cere obligatoriu sortare prin interclasare.

Exemplu:

Intrare:

6
5 2 8 1 9 3

Ieșire:

1 2 3 5 8 9

Cum gândim soluția:

Declarăm vectorul v și auxiliarul temp globale
Scriem interclaseaza(st, mij, dr) cu cei doi indici
Scriem mergeSort(st, dr): dacă st < dr, împărțim și apelăm recursiv
Afișăm vectorul sortat

Scrie soluția în C++:

Soluție corectă:

#include <iostream>
using namespace std;

int v[1001], temp[1001];

void interclaseaza(int st, int mij, int dr) {
    int i = st, j = mij + 1, k = st;
    while (i <= mij && j <= dr) {
        if (v[i] < v[j]) {
            temp[k++] = v[i++];
        } else {
            temp[k++] = v[j++];
        }
    }
    while (i <= mij) {
        temp[k++] = v[i++];
    }
    while (j <= dr) {
        temp[k++] = v[j++];
    }
    for (int p = st; p <= dr; p++) {
        v[p] = temp[p];
    }
}

void mergeSort(int st, int dr) {
    if (st < dr) {
        int mij = (st + dr) / 2;
        mergeSort(st, mij);
        mergeSort(mij + 1, dr);
        interclaseaza(st, mij, dr);
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    mergeSort(1, n);
    for (int i = 1; i <= n; i++) {
        cout << v[i] << " ";
    }
    return 0;
}

Ce învățăm: interclasarea se face în vectorul auxiliar temp, care este apoi copiat înapoi în v pe intervalul [st, dr].

PbInfo - Interclasare

Enunț:

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

Date de intrare:

Programul citește n și cele n elemente ale primului șir, apoi m și cele m elemente ale celui de-al doilea șir.

Date de ieșire:

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

Restricții și precizări:

1 ≤ n, m ≤ 1000; ambele șiruri sunt sortate crescător.

Exemplu:

Intrare:

Ieșire:

1 2 3 4 5 6 7

Cum gândim soluția:

Folosim doi indici i și j pentru cele două șiruri
Copiem elementul mai mic în c și înaintăm
Copiem elementele rămase dintr-un șir atunci când celălalt se epuizează
Afișăm vectorul c

Scrie soluția în C++:

Soluție corectă:

#include <iostream>
using namespace std;

int a[1001], b[1001], c[2002];

int main() {
    int n, m;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }
    int i = 1, j = 1, k = 0;
    while (i <= n && j <= m) {
        if (a[i] < b[j]) {
            c[++k] = a[i++];
        } else {
            c[++k] = b[j++];
        }
    }
    while (i <= n) {
        c[++k] = a[i++];
    }
    while (j <= m) {
        c[++k] = b[j++];
    }
    for (int p = 1; p <= k; p++) {
        cout << c[p] << " ";
    }
    return 0;
}

Ce învățăm: interclasarea este operația de combinare din merge sort; aici o folosim direct pe două șiruri deja sortate.

EXERCIȚII PRACTICE

Exercițiul Practic: variante de interclasare

Sarcini de lucru

Rezolvă sarcinile de mai jos pentru a exersa merge sort și interclasarea

Sarcina 1: Merge sort descrescător

Cerință: Modifică programul de sortare prin interclasare astfel încât vectorul să fie sortat descrescător. Scrie programul complet.

Scrie programul C++ aici:

Soluție pentru Sarcina 1:

Sugestie: se modifică doar comparația din interclasare: copiem elementul mai mare în locul celui mai mic.

#include <iostream>
using namespace std;

int v[1001], temp[1001];

void interclaseaza(int st, int mij, int dr) {
    int i = st, j = mij + 1, k = st;
    while (i <= mij && j <= dr) {
        if (v[i] > v[j]) {
            temp[k++] = v[i++];
        } else {
            temp[k++] = v[j++];
        }
    }
    while (i <= mij) {
        temp[k++] = v[i++];
    }
    while (j <= dr) {
        temp[k++] = v[j++];
    }
    for (int p = st; p <= dr; p++) {
        v[p] = temp[p];
    }
}

void mergeSort(int st, int dr) {
    if (st < dr) {
        int mij = (st + dr) / 2;
        mergeSort(st, mij);
        mergeSort(mij + 1, dr);
        interclaseaza(st, mij, dr);
    }
}

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
    }
    mergeSort(1, n);
    for (int i = 1; i <= n; i++) {
        cout << v[i] << " ";
    }
    return 0;
}

Verifică: pentru v = 5 2 8 1, rezultatul descrescător este 8 5 2 1. Diferența față de varianta crescătoare este doar operatorul > din interclasare.

Sarcina 2: Interclasare fără duplicate

Cerință: Se citesc două șiruri sortate crescător (pot avea elemente comune). Afișează elementele interclasate fără valori duplicate.

Scrie programul C++ aici:

Soluție pentru Sarcina 2:

#include <iostream>
using namespace std;

int a[1001], b[1001], c[2002];

int main() {
    int n, m;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    cin >> m;
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
    }
    int i = 1, j = 1, k = 0;
    while (i <= n && j <= m) {
        if (a[i] < b[j]) {
            c[++k] = a[i++];
        } else {
            if (a[i] > b[j]) {
                c[++k] = b[j++];
            } else {
                c[++k] = a[i++];
                j++;
            }
        }
    }
    while (i <= n) {
        c[++k] = a[i++];
    }
    while (j <= m) {
        c[++k] = b[j++];
    }
    for (int p = 1; p <= k; p++) {
        cout << c[p] << " ";
    }
    return 0;
}

Verifică: pentru a = 1 2 3 și b = 2 4, rezultatul este 1 2 3 4; la egalitate copiem o singură dată valoarea și înaintăm ambii indici.

SCRIE PE CAIET

Scrie pe caiet - Sortarea prin interclasare (merge sort)

Titlul lecției

Ora 3: Sortarea prin interclasare (merge sort)

Definiția lecției

Merge sort este un algoritm de sortare de tip Divide et impera, cu complexitatea O(n log n). Vectorul se împarte la jumătate până rămân elemente individuale (un singur element este deja sortat), apoi, la întoarcere, fiecare pereche de jumătăți sortate se interclasează într-o singură secvență ordonată. Interclasarea folosește doi indici (i în jumătatea stângă, j în cea dreaptă) și un vector auxiliar temp, copiind la fiecare pas elementul mai mic, apoi elementele rămase dintr-o jumătate epuizată. La final, temp se copiază înapoi în vectorul inițial. Din această lecție rămân în caiet funcția interclaseaza(st, mij, dr) completă, funcția mergeSort(st, dr) și apelul din main().

Definiții esențiale

Sortarea prin interclasare (merge sort): algoritm de sortare de tip Divide et impera care împarte vectorul în două jumătăți, sortează recursiv fiecare jumătate, apoi le interclasează într-o singură secvență sortată.
Interclasare: operația de îmbinare a două secvențe deja sortate, alegând la fiecare pas cel mai mic element dintre „capetele" celor două secvențe.
Vector auxiliar: tabloul temp în care se construiește secvența interclasată, apoi se copiază înapoi în v.
Complexitate: timp O(n log n), spațiu O(n).

Algoritmul cheie - pseudocod

mergeSort(st, dr): dacă st < dr, calculează mij, apelează recursiv mergeSort(st, mij) și mergeSort(mij + 1, dr), apoi interclaseaza(st, mij, dr).
interclaseaza(st, mij, dr): cu trei indici (i în stânga, j în dreapta, k în temp), copiază elementul mai mic; la final copiază restul și readuce temp în v.

Algoritmul cheie - cod C++

Declară global int v[1001], temp[1001];.
Implementează void interclaseaza(int st, int mij, int dr) cu trei bucle while (comparație, restul stâng, restul drept) și copierea finală cu for.
Implementează void mergeSort(int st, int dr) cu if (st < dr) ca pas de divizare.
În main(): citește, apelează mergeSort(1, n) și afișează vectorul sortat.

Greșeli comune de evitat

Condiția st <= dr în loc de st < dr la mergeSort provoacă recursivitate infinită.
Uitarea ultimelor două bucle while care copiază elementele rămase într-o secvență epuizată.
Uitarea copierii finale din temp în v: fără ea, vectorul nu rămâne sortat între niveluri.
Amestecarea indicilor (k folosit ca i sau j) în interclasare duce la valori greșite.

Sfaturi practice și trucuri

Testează interclasarea separat, pe două secvențe deja sortate, înainte de a testa întreaga sortare.
Urmărește pașii pe un vector cu 4 elemente și desenează arborele de apeluri pentru a înțelege ordinea.
Reține: complexitatea O(n log n) se justifică la oral spunând „n elemente pe fiecare dintre cele log₂(n) niveluri".
Pentru n mare (100000 de elemente), merge sort rămâne rapid, în timp ce sortările pătratice devin impracticabile.

Exemplu practic

Secretariatul școlii are două liste de elevi, fiecare sortată alfabetic, pe care trebuie să le îmbine într-o singură listă ordonată. Procedeul manual — compararea numelor de la începutul fiecărei liste și mutarea celui mai mic — este exact interclasarea, implementată în funcția de mai jos (cu tablourile globale v și temp):

C++ - interclasarea a două jumătăți sortate

void interclaseaza(int st, int mij, int dr) {
    int i = st, j = mij + 1, k = st;
    while (i <= mij && j <= dr) {
        if (v[i] <= v[j]) {
            temp[k++] = v[i++];
        } else {
            temp[k++] = v[j++];
        }
    }
    while (i <= mij) {
        temp[k++] = v[i++];
    }
    while (j <= dr) {
        temp[k++] = v[j++];
    }
    for (int p = st; p <= dr; p++) {
        v[p] = temp[p];
    }
}

Ora 3: Sortarea prin interclasare (merge sort)

Înainte de a începe

Ce știi deja?

Ce vei învăța astăzi?

Ideea metodei

Analogie: îmbinarea a două grămezi de cartonașe ordonate

Exemplu: interclasarea a două secvențe

Funcția de interclasare

interclasarea secvențelor [1, 3, 5] și [2, 4]

Programul complet: merge sort

Exercițiu de completare

Completează descrierea sortării prin interclasare:

Bancă de cuvinte:

Exercițiu de completare: codul interclasării

Completează descrierea funcției de interclasare:

Bancă de cuvinte:

Test de înțelegere

Test rapid - merge sort:

Aprofundare

PbInfo - Sortare (merge sort)

Enunț:

Date de intrare:

Date de ieșire:

Restricții și precizări:

Exemplu:

Cum gândim soluția:

Scrie soluția în C++:

Soluție corectă:

PbInfo - Interclasare

Enunț:

Date de intrare:

Date de ieșire:

Restricții și precizări:

Exemplu:

Cum gândim soluția:

Scrie soluția în C++:

Soluție corectă:

Exercițiul Practic: variante de interclasare

Sarcini de lucru

Sarcina 1: Merge sort descrescător

Soluție pentru Sarcina 1:

Sarcina 2: Interclasare fără duplicate

Soluție pentru Sarcina 2:

Scrie pe caiet - Sortarea prin interclasare (merge sort)

Titlul lecției

Definiția lecției

Definiții esențiale

Algoritmul cheie - pseudocod

Algoritmul cheie - cod C++

Greșeli comune de evitat

Sfaturi practice și trucuri

Exemplu practic