🔢

Vreau sa sortez elementele!

Dupa aceasta lectie, vei sti sa ordonezi elementele unui tablou crescator sau descrescator folosind algoritmul Bubble Sort.

INCEARCA

Gandeste-te la asta!

Provocarea ta:

Ai numerele: 5, 2, 8, 1, 9

Cum le-ai ordona crescator (de la mic la mare)?

Gandeste: Ce pasi ai urma?
Ai compara doua numere vecine si le-ai interschimba daca nu sunt in ordine?

Click pentru indiciu

Imagineaza-te ca ai baloane cu numere - cele mai usoare (mici) se ridica sus!

Compari 5 cu 2: 5 > 2, deci le interschimbi: 2, 5, 8, 1, 9

Compari 5 cu 8: 5 < 8, OK, nu schimbi nimic

Continui pana nu mai ai ce interschimba...

INVATA

Algoritmul Bubble Sort

Bubble Sort (Sortare prin metoda bulelor)

Bubble Sort este un algoritm simplu de sortare care:

Compara doua elemente vecine
Daca nu sunt in ordine, le interschimba
Repeta pana tabloul este sortat

Se numeste "bubble" (bula) pentru ca elementele mari "se ridica" spre sfarsit ca bulele de aer in apa!

Pasii algoritmului

1

Parcurge tabloul de la inceput

2

Compara fiecare element cu vecinul sau din dreapta

3

Daca sunt in ordine gresita, interschimba-le

4

Repeta parcurgerea pana nu mai faci nicio interschimbare

Demo interactiv: Bubble Sort

5 [0]

2 [1]

8 [2]

1 [3]

9 [4]

Click pe "Sorteaza pas cu pas" pentru a vedea algoritmul in actiune!

Interschimbarea a doua valori

// Pentru a interschimba a si b, avem nevoie de o variabila auxiliara
int aux = a;   // salvam valoarea lui a
a = b;         // a primeste valoarea lui b
b = aux;       // b primeste vechea valoare a lui a

// Exemplu cu tablou:
int aux = note[i];
note[i] = note[i+1];
note[i+1] = aux;
                    

Codul Bubble Sort (crescator)

int note[5] = {5, 2, 8, 1, 9};
int n = 5;

// Sortare crescatoare
for(int i = 0; i < n - 1; i++) {
    for(int j = 0; j < n - i - 1; j++) {
        if(note[j] > note[j+1]) {
            // Interschimbare
            int aux = note[j];
            note[j] = note[j+1];
            note[j+1] = aux;
        }
    }
}

// Rezultat: 1, 2, 5, 8, 9
                    

Sortare DESCRESCATOARE

// Schimbam doar conditia: > devine <
for(int i = 0; i < n - 1; i++) {
    for(int j = 0; j < n - i - 1; j++) {
        if(note[j] < note[j+1]) {  // < in loc de >
            int aux = note[j];
            note[j] = note[j+1];
            note[j+1] = aux;
        }
    }
}
// Rezultat: 9, 8, 5, 2, 1
                    

De ce n-1 si n-i-1?

n-1: Dupa n-1 parcurgeri, tabloul e garantat sortat

n-i-1: Dupa fiecare parcurgere, ultimele i elemente sunt deja sortate (cele mai mari au "plutit" la final)

Exemplu complet

#include <iostream>
using namespace std;

int main() {
    int note[100];
    int n;

    cout << "Cate numere? ";
    cin >> n;

    for(int i = 0; i < n; i++) {
        cout << "Numarul " << i + 1 << ": ";
        cin >> note[i];
    }

    // Bubble Sort crescator
    for(int i = 0; i < n - 1; i++) {
        for(int j = 0; j < n - i - 1; j++) {
            if(note[j] > note[j+1]) {
                int aux = note[j];
                note[j] = note[j+1];
                note[j+1] = aux;
            }
        }
    }

    cout << "Numerele sortate crescator: ";
    for(int i = 0; i < n; i++) {
        cout << note[i] << " ";
    }

    return 0;
}
                    

VERIFICA

Hai sa vedem ce ai retinut!

1. Ce face algoritmul Bubble Sort?

Cauta un element in tablou

Ordoneaza elementele comparand vecini si interschimband

Gaseste elementul maxim

2. Pentru sortare DESCRESCATOARE, ce conditie folosim?

if(note[j] > note[j+1])

if(note[j] < note[j+1])

if(note[j] == note[j+1])

3. De ce avem nevoie de o variabila auxiliara la interschimbare?

Pentru a nu pierde valoarea unuia dintre elemente

Pentru a face codul mai lung

Nu avem nevoie, putem face fara

4. Dupa sortare crescatoare a {5, 2, 8, 1}, care este ordinea?

8, 5, 2, 1

1, 2, 5, 8

5, 2, 8, 1

🎉

Felicitari!

Ai terminat Lectia 5: Sortarea tablourilor

+50 XP

Acum stii algoritmul Bubble Sort pentru a ordona elemente!

Continua la Proiectul Final