Lectia 5: Sortarea Tablourilor | TIC Clasa a VIII-a

Incearca singur!

🎯 INCEARCA

Testeaza inainte sa inveti!

Nu trebuie sa intelegi totul acum. Doar copiaza, ruleaza si observa ce se intampla cu numerele.

Misiunea ta (7 minute):

Copiaza codul de mai jos si lipeste-l pe OneCompiler. Apasa Run. Observa cum numerele se rearanjeaza!

#include <iostream>
using namespace std;

int main() {
    int a[5] = {5, 3, 8, 1, 4};
    int n = 5;

    cout << "Inainte de sortare: ";
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;

    // Bubble Sort
for (int p = 0; p < n - 1; p++) {
        for (int i = 0; i < n - 1 - p; i++) {
            if (a[i] > a[i + 1]) {
                int temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
            }
        }
    }

    cout << "Dupa sortare:       ";
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}

▶ Deschide OneCompiler

Adauga in interiorul buclei exterioare (dupa bucla for interioara) urmatoarele linii pentru a vedea tabloul dupa fiecare trecere:
cout << "Dupa trecerea " << p+1 << ": ";
for (int j = 0; j < n; j++) cout << a[j] << " ";
cout << endl;

Schimba conditia din if (a[i] > a[i+1]) in if (a[i] < a[i+1]). Ruleaza. Ce observi? Ordinea s-a schimbat?

Schimba valorile initiale ale tabloului in: {10, 9, 8, 7, 6} (deja sortat descrescator). Ruleaza cu > in conditie. Cate treceri sunt necesare?

Acum incearca cu tabloul {1, 2, 3, 4, 5} (deja sortat crescator). Ruleaza. Se fac interschimbari? Ce observi la treceri?

🌟 BONUS: Adauga un contor care numara cate interschimbari (swap-uri) se fac in total. Declara int swaps = 0; si incrementeaza-l (swaps++;) de fiecare data cand se face o interschimbare.

▶ Blocat la pasul 2? Click aici pentru un indiciu

Adauga cele 3 linii imediat dupa acolada } care inchide bucla for interioara (cea cu i), dar inainte de acolada } care inchide bucla exterioara (cea cu p).

Ar trebui sa vezi 4 linii de output (4 treceri pentru 5 elemente), plus starea initiala si cea finala.

▶ Blocat la pasul 3? Click aici

Cand schimbi > in <, algoritmul muta elementele mici la sfarsit in loc de cele mari. Rezultatul: sortare descrescatoare (de la mare la mic): 8 5 4 3 1.

Asta e tot ce trebuie schimbat! Un singur caracter face diferenta intre crescator si descrescator.

▶ Blocat la pasul 5? Click aici

Cand tabloul este deja sortat, conditia a[i] > a[i+1] nu este niciodata adevarata, deci nicio interschimbare nu are loc. Totusi, algoritmul face toate trecerile (n-1 = 4), chiar daca nu schimba nimic.

Aceasta este o slabiciune a Bubble Sort de baza. Exista o optimizare: daca intr-o trecere nu s-a facut nicio interschimbare, tabloul este deja sortat si putem opri.

De ce conteaza sortarea?

Sortarea inseamna aranjarea elementelor unui tablou intr-o ordine logica: de la mic la mare (crescator) sau de la mare la mic (descrescator).

Sortarea este una dintre cele mai importante operatii in informatica. Gandeste-te:

Dictionarul - cuvintele sunt sortate alfabetic, altfel nu ai gasi niciodata nimic
Catalogul scolar - elevii sunt sortati alfabetic dupa nume
Clasament sportiv - echipele sunt sortate dupa punctaj
Preturile pe un site - sortezi produsele de la ieftin la scump
Notele la examen - profesorul le sorteaza pentru a calcula statistici

🎲 Analogie: Cartile de joc

Cand primesti carti de joc, le aranjezi in mana in ordine (2, 3, 4, ..., A). Faci asta automat: compari doua carti, daca sunt in ordine gresita le interschimbi. Exact asta face Bubble Sort!

Cum interschimbam doua valori?

Inainte de a invata sortarea, trebuie sa stim cum interschimbam (swap) doua valori. Nu putem face direct a = b; b = a; pentru ca am pierde valoarea lui a!

Avem nevoie de o variabila temporara (temp) - ca un pahar gol in care punem temporar o valoare.

☕ Analogie: Doua pahare cu lichid

Ai un pahar cu suc de portocale (A) si un pahar cu suc de mere (B). Vrei sa le interschimbi. Nu poti turna A in B direct (se amesteca!). Ai nevoie de un pahar gol (temp): torni A in paharul gol, apoi B in A, apoi din paharul gol in B. Gata!

Algoritmul Bubble Sort

Bubble Sort (sortarea prin metoda bulelor) functioneaza astfel:

Parcurgem tabloul de la stanga la dreapta
Comparam fiecare element cu vecinul sau din dreapta
Daca sunt in ordine gresita, le interschimbam
Repetam de la pas 1 pana cand totul e sortat

De ce se numeste "Bubble" (bula)? Pentru ca la fiecare trecere, cel mai mare element "pluteste" in sus (spre sfarsitul tabloului), ca o bula de aer care urca in apa!

Programul complet: Bubble Sort crescator

Sa punem totul impreuna. Urmareste fiecare linie si rolul ei:

Program complet - ruleaza-l!

#include <iostream>
using namespace std;

int main() {
    // Pasul 1: Declaram tabloul si dimensiunea
int a[5] = {5, 3, 8, 1, 4};
    int n = 5;

    // Pasul 2: Afisam tabloul inainte de sortare
    cout << "Inainte: ";
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;

    // Pasul 3: Bubble Sort - sortare crescatoare
for (int p = 0; p < n - 1; p++) {          // n-1 treceri
for (int i = 0; i < n - 1 - p; i++) {  // comparam perechi
if (a[i] > a[i + 1]) {            // ordine gresita?
int temp = a[i];               // salveaza
                a[i] = a[i + 1];               // suprascrie
                a[i + 1] = temp;               // restaureaza
            }
        }
    }

    // Pasul 4: Afisam tabloul dupa sortare
    cout << "Dupa:    ";
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}

▶ Ruleaza pe OneCompiler

Un singur caracter face diferenta!

Pentru a schimba directia sortarii, modifici doar operatorul de comparatie din conditia if:

Sortare CRESCATOARE (mic la mare)

if (a[i] > a[i + 1])   // Daca e mai MARE decat vecinul
// Rezultat: 1, 3, 4, 5, 8

Sortare DESCRESCATOARE (mare la mic)

if (a[i] < a[i + 1])   // Daca e mai MIC decat vecinul
// Rezultat: 8, 5, 4, 3, 1

💡 Cum sa retii?

Crescator = vrem cele mici in fata, deci mutam cele mari spre sfarsit → folosim >
Descrescator = vrem cele mari in fata, deci mutam cele mici spre sfarsit → folosim <

Regula n - 1 treceri

Pentru un tablou de n elemente, Bubble Sort face maxim n - 1 treceri.

De ce? Pentru ca la fiecare trecere, cel putin un element ajunge la locul lui final. Dupa n-1 elemente asezate corect, ultimul este automat la locul lui.

n (elemente)	Treceri (n-1)	Comparatii totale (cel mai rau caz)
3	2	2 + 1 = 3
5	4	4 + 3 + 2 + 1 = 10
10	9	9 + 8 + ... + 1 = 45
100	99	99 + 98 + ... + 1 = 4950

💡 De ce bucla interioara scade? (n - 1 - p)

Dupa trecerea 1, ultimul element e sortat. Dupa trecerea 2, ultimele 2 sunt sortate. Dupa trecerea p, ultimele p elemente sunt sortate. Deci nu mai avem nevoie sa le comparam!

De aceea scriem i < n - 1 - p si nu i < n - 1. Functioneaza si cu i < n - 1, dar face comparatii inutile.

Citim n numere, le sortam si le afisam

In practica, nu scriem valorile direct in cod. Le citim de la tastatura:

Program complet cu citire

#include <iostream>
using namespace std;

int main() {
    int n;
    cout << "Cate numere vrei sa sortezi? ";
    cin >> n;

    int a[100]; // tablou de maxim 100 elemente
    cout << "Introdu " << n << " numere: ";
    for (int i = 0; i < n; i++)
        cin >> a[i];

    // Bubble Sort - crescator
for (int p = 0; p < n - 1; p++) {
        for (int i = 0; i < n - 1 - p; i++) {
            if (a[i] > a[i + 1]) {
                int temp = a[i];
                a[i] = a[i + 1];
                a[i + 1] = temp;
            }
        }
    }

    cout << "Tabloul sortat: ";
    for (int i = 0; i < n; i++)
        cout << a[i] << " ";
    cout << endl;

    return 0;
}

▶ Ruleaza pe OneCompiler

Exercitii practice

Exercitiul 1 (Nivel minim) - Trasarea Bubble Sort

Traseaza manual algoritmul Bubble Sort (crescator) pe tabloul:

int a[6] = {9, 2, 7, 4, 1, 5};

Scrie starea tabloului dupa fiecare trecere (sunt maxim 5 treceri). Noteaza si cate interschimbari s-au facut in fiecare trecere.
Cate comparatii totale se fac? (Aduna: trecerea 1 are 5 comparatii, trecerea 2 are 4, ...)
Cate interschimbari totale se fac?
La ce trecere a ajuns elementul 9 pe ultima pozitie?

Raspunde numerotat: 1. ... 2. ... 3. ... 4. ...

Exercitiul 2 (Nivel standard) - Programeaza cu Bubble Sort

Cerinta: Scrie un program C++ care citeste n numere de la tastatura, le sorteaza descrescator si afiseaza tabloul sortat. In plus, afiseaza si cate interschimbari au fost necesare.

Exemplu input/output:

Cate numere? 5
Introdu 5 numere: 3 7 1 9 4
Tablou sortat descrescator: 9 7 4 3 1
Interschimbari efectuate: 6

Indicii:

Porneste de la programul complet din lectie si schimba > in <
Adauga un contor int swaps = 0; si incrementeaza-l cu swaps++; la fiecare interschimbare
Afiseaza contorul la sfarsit: cout << "Interschimbari: " << swaps;

Exercitiul 3 (Nivel performanta) - Explicatie scrisa

Cerinta: Explica in cuvintele tale cum functioneaza algoritmul Bubble Sort. Raspunde la urmatoarele intrebari:

De ce se numeste "Bubble" (bula)? Ce analogie din viata reala ti se pare potrivita?
De ce este necesar sa facem mai multe treceri prin tablou, nu doar una singura?
De ce scade numarul de comparatii la fiecare trecere (de ce scriem n - 1 - p si nu n - 1)?
Care este cel mai bun caz (cand tabloul e deja sortat) si cel mai rau caz (cand e sortat invers) pentru Bubble Sort? Ce diferente sunt?

Cuvinte cheie de folosit: trecere, comparatie, interschimbare, variabila temporara, crescator, descrescator, adiacent, element maxim

Ce ai invatat astazi

Ai invatat de ce conteaza sortarea

Acum stii cum interschimbam doua valori

Ai descoperit algoritmul bubble sort

Ai explorat programul complet: bubble sort crescator

Ai inteles un singur caracter face diferenta

Ai invatat regula n - 1 treceri

Acum stii citim n numere, le sortam si le afisam

Vreau sa pun datele in ordine!

Obiectivul lectiei

Dupa aceasta lectie vei putea: