Invatare Atomica ⭐ Continut extra-curricular

Vreau sa pun datele in ordine!

ℹ️ Nota: continut extracurricular (aprofundare)

Algoritmii de sortare nu fac parte din programa oficiala OMEN 3393/2017 pentru clasa a VIII-a. Aceasta lectie este material de aprofundare, recomandat elevilor curioasi sau celor care se pregatesc pentru concursuri. Daca esti la inceput, poti reveni dupa ce ai terminat lectiile obligatorii.

Progres lectie:
0%
🎯

Obiectivul lectiei

Imagineaza-ti ca ai 30 de lucrari de examen cu note si trebuie sa le aranjezi de la cea mai mica la cea mai mare nota. Cum faci?

Dupa aceasta lectie vei putea:

  • Sa explici de ce conteaza sortarea
  • Sa explici cum interschimbam doua valori
  • Sa implementezi algoritmul bubble sort
  • Sa aplici programul complet: bubble sort crescator
  • Sa aplici un singur caracter face diferenta

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):
1
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
2
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;
3
Schimba conditia din if (a[i] > a[i+1]) in if (a[i] < a[i+1]). Ruleaza. Ce observi? Ordinea s-a schimbat?
4
Schimba valorile initiale ale tabloului in: {10, 9, 8, 7, 6} (deja sortat descrescator). Ruleaza cu > in conditie. Cate treceri sunt necesare?
5
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.

1

De ce conteaza sortarea?

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: Bule de aer in apa

Imagineaza-ti mai multe bule de aer de marimi diferite intr-un pahar cu apa. La fiecare moment, bula cea mai mare pluteste spre suprafata, impingand-o pe cea mai mica sub ea. Exact asa functioneaza Bubble Sort: la fiecare trecere prin tablou, comparam fiecare pereche de vecini si, daca sunt in ordine gresita, le interschimbam — astfel cel mai mare element "pluteste" spre sfarsitul tabloului, ca o bula de aer care urca in apa.

Nota: Cand oamenii sorteaza carti in mana, ei folosesc intuitiv un algoritm diferit — iau o carte si o introduc la locul potrivit intre celelalte (acela se numeste Insertion Sort). Bubble Sort este un algoritm sistematic pe care calculatoarele il pot executa eficient pas cu pas, dar oamenii il folosesc rar in mod natural.

2

Cum interschimbam doua valori?

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!

3

Algoritmul Bubble Sort

Algoritmul Bubble Sort

Bubble Sort (sortarea prin metoda bulelor) functioneaza astfel:

  1. Parcurgem tabloul de la stanga la dreapta
  2. Comparam fiecare element cu vecinul sau din dreapta
  3. Daca sunt in ordine gresita, le interschimbam
  4. 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!

4

Programul complet: Bubble Sort crescator

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
5

Un singur caracter face diferenta!

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 <

6

Regula n - 1 treceri

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.

🔭 Aprofundare: exista si alti algoritmi de sortare

Bubble Sort este cel mai simplu de inteles, dar si cel mai lent pentru liste mari (face multe comparatii inutile). In informatica exista multi alti algoritmi de sortare, fiecare cu avantaje proprii:

  • Selection Sort — la fiecare trecere gaseste minimul si il pune pe locul corect
  • Insertion Sort — ia pe rand fiecare element si il insereaza la locul potrivit (asa sorteaza oamenii cartile in mana!)
  • Quick Sort — divide tabloul in doua parti si sorteaza recursiv; folosit in practica

Acestea sunt subiecte de aprofundare pentru cine vrea sa mearga mai departe (liceu, concursuri). Deocamdata, Bubble Sort este suficient pentru a intelege principiul sortarii.

7

Citim n numere, le sortam si le afisam

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};
  1. Scrie starea tabloului dupa fiecare trecere (sunt maxim 5 treceri). Noteaza si cate interschimbari s-au facut in fiecare trecere.
  2. Cate comparatii totale se fac? (Aduna: trecerea 1 are 5 comparatii, trecerea 2 are 4, ...)
  3. Cate interschimbari totale se fac?
  4. 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:

  1. De ce se numeste "Bubble" (bula)? Ce analogie din viata reala ti se pare potrivita?
  2. De ce este necesar sa facem mai multe treceri prin tablou, nu doar una singura?
  3. De ce scade numarul de comparatii la fiecare trecere (de ce scriem n - 1 - p si nu n - 1)?
  4. 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

Urmatoarea lectie

Continua cu lectia urmatoare pentru a aprofunda cunostintele.

Continua →