Școala Româno-Britanică
Modulul 4 Clasa a IX-a | Python

Ora 5: Metoda bulelor

Ce vei învăța astăzi: Sortarea prin metoda bulelor

Rezultat practic: Sortezi o listă prin metoda bulelor, comparând și interschimbând elemente adiacente (Competența 3.2).

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

Înainte de a începe

De ce contează? Metoda bulelor arată cel mai clar cum se compară și se mută elementele pas cu pas și este des cerută la teste pentru că poate fi urmărită manual pe hârtie. Comparând vecinii, înțelegi exact de ce valorile „urcă" la locul lor.

Ce știi deja?

La ora 3 ai învățat selecția minimului și interschimbarea a, b = b, a. Acum interschimbarea se aplică vecinilor, nu minimului găsit: ce făcea selecția minimului la fiecare pas?

Ideea-cheie: Comparăm elemente vecine și le interschimbăm dacă sunt în ordine greșită; după fiecare parcurgere, cel mai mare element rămas ajunge pe ultima poziție.
SINTEZĂ TEORETICĂ ȘI EXEMPLE GHIDATE

Ce vei învăța astăzi?

După această lecție vei învăța să sortezi o listă prin metoda bulelor (compararea elementelor vecine și interschimbarea lor cât timp sunt în ordine greșită), înțelegând de ce elementele „urcă" la locul lor și cum se repetă parcurgerile.

Ideea metodei bulelor
De ce elementele „urcă" ca niște bule
Parcurgeri repetate ale listei
Comparația cu selecția minimului

Ideea metodei bulelor

Definiție: Comparăm elemente vecine (adiacente) și le schimbăm între ele dacă sunt în ordine greșită. După fiecare parcurgere (o trecere completă prin listă, de la primul la ultimul element), cea mai mare valoare „urcă" la finalul listei.

De ce „bulele"?

Este ca bulele de aer într-un pahar cu apă: cele mai mari ajung primele la suprafață. La fiecare parcurgere, cel mai mare element rămas ajunge la capătul listei, ca o bulă care urcă.

Parcurgeri repetate

Facem mai multe parcurgeri. La prima parcurgere, cel mai mare element ajunge pe ultima poziție. La a doua, următorul cel mai mare pe penultima, și tot așa.

Exemplu: metoda bulelor

pentru i = 1, n - 1 execută pentru j = 1, n - i execută dacă v[j] > v[j + 1] atunci v[j] <-> v[j + 1]
Python - metoda bulelor
v = [6, 2, 8, 4, 1]
n = len(v)

for i in range(n - 1):
    for j in range(n - 1 - i):
        if v[j] > v[j + 1]:
            v[j], v[j + 1] = v[j + 1], v[j]

print(v)

Observă: bucla interioară merge doar până la n - 1 - i, pentru că ultimele i elemente sunt deja pe poziția finală.

Prima parcurgere pe [6, 2, 8, 4, 1]
1Comparăm 6 și 2: le schimbăm => 2 6 8 4 1
2Comparăm 6 și 8: ordine bună => 2 6 8 4 1
3Comparăm 8 și 4: le schimbăm => 2 6 4 8 1
4Comparăm 8 și 1: le schimbăm => 2 6 4 1 8

Exemplu pe șir

Urmărim toate parcurgerile pentru [6, 2, 8, 4, 1] și vedem cum se așază valorile mari la coadă:

Parcurgerea Lista după parcurgere Ce s-a fixat
1 2 6 4 1 8 8 (maximul) pe ultima poziție
2 2 4 1 6 8 6 pe poziția finală
3 2 1 4 6 8 4 pe poziția finală
4 1 2 4 6 8 2 pe poziția finală

Comparația cu selecția minimului

Criteriu Metoda bulelor Selecția minimului
Ce facem Comparăm vecini și îi schimbăm Căutăm minimul și îl punem la locul lui
Interschimbări Multe, ori de câte ori vecinii sunt în dezordine Una pe pas, maximum
Când o alegem Când vrem să observăm evoluția pas cu pas Când vrem mai puține interschimbări

Exercițiu de completare

Completează descrierea metodei bulelor:

Comparăm elemente ______. Dacă v[j] ______ v[j+1], le ______. Bucla exterioară merge de la 0 la ______.

Bancă de cuvinte:
adiacente > schimb n-1

Test de înțelegere

Test rapid - metoda bulelor:

1. În metoda bulelor comparăm:

2. După prima parcurgere, cel mai mare element se află:

3. Dacă într-o parcurgere nu s-a făcut nicio interschimbare, atunci:

Test suplimentar - verifică ce ai reținut

Test rapid suplimentar - metoda bulelor:

1. La metoda bulelor comparăm:

2. După o parcurgere completă, cel mai mare element:

3. Dacă într-o parcurgere nu se face nicio interschimbare:

Ai grijă la: limitează bucla interioară la n - 1 - i. Dacă o lași să meargă până la n, compari și elemente deja așezate pe poziția finală și riști accesul în afara listei.

Aprofundare

Metoda bulelor poate fi optimizată: dacă într-o parcurgere completă nu s-a făcut nicio interschimbare, înseamnă că lista este deja sortată și putem opri algoritmul mai devreme, economisind timp pe liste aproape sortate.

  • Optimizarea cu un steag: folosim o variabilă schimbat = False la începutul fiecărei parcurgeri; dacă se face vreo interschimbare, o setăm pe True. Dacă la final rămâne False, oprim buclele.
  • Cazul cel mai bun: dacă lista este deja sortată, varianta optimizată face o singură parcurgere, cu n-1 comparații și zero interschimbări.
  • Numărul de comparații: fără optimizare, se fac mereu n(n-1)/2 comparații; numărul de interschimbări depinde de date și poate fi mult mai mic.
  • Sortarea descrescătoare: se obține schimbând condiția v[j] > v[j + 1] în v[j] < v[j + 1]; atunci cele mai mici valori „urcă" la final.
  • De ce n-1-i: după parcurgerea i, ultimele i elemente sunt fixate pe pozițiile finale, deci bucla interioară nu mai trebuie să le atingă.
  • Comparația cu selecția minimului: ambele fac același număr de comparații, dar bulele face în general mult mai multe interschimbări (una de fiecare dată când vecinii sunt în dezordine).
APLICARE ȘI REZOLVARE DE PROBLEME

PbInfo - Sortare prin metoda bulelor

Enunț:

Cerință: Se citește numărul natural n și apoi n numere întregi. Să se sorteze crescător vectorul folosind metoda bulelor și să se afișeze.

Date de intrare:

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

Date de ieșire:

Programul va afișa cele n numere sortate crescător, separate prin spații.

Restricții și precizări:

n este un număr natural, cu 1 <= n <= 1000, iar elementele sunt numere întregi.

Exemplu:

Intrare:

5
6 2 8 4 1

Ieșire:

1 2 4 6 8
Cum gândim soluția:
  1. Citim n și vectorul v
  2. Repetăm n-1 parcurgeri, comparând vecinii
  3. La fiecare parcurgere mergem doar până la n-1-i
  4. Afișăm vectorul sortat
Scrie soluția în Python:
Soluție corectă:
Soluție Python
n = int(input())
v = list(map(int, input().split()))

for i in range(n - 1):
    for j in range(n - 1 - i):
        if v[j] > v[j + 1]:
            v[j], v[j + 1] = v[j + 1], v[j]

for x in v:
    print(x, end=" ")

Ce învățăm: folosim două bucle: una pentru parcurgeri (i) și una pentru vecinii care se compară (j), cu limita n-1-i pentru eficiență.

PbInfo - Verificare sortare crescătoare

Enunț:

Cerință: Se citește numărul natural n și apoi n numere întregi. Să se verifice dacă vectorul este sortat crescător.

Date de intrare:

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

Date de ieșire:

Programul va afișa DA dacă vectorul este sortat crescător, altfel NU.

Restricții și precizări:

n este un număr natural, cu 1 <= n <= 1000, iar elementele sunt numere întregi.

Exemplu:

Intrare:

5
1 3 5 7 9

Ieșire:

DA
Cum gândim soluția:
  1. Presupunem că vectorul este sortat (sortat = True)
  2. Verificăm toate perechile v[i] și v[i+1]
  3. Dacă găsim v[i] > v[i+1], vectorul nu este sortat
Scrie soluția în Python:
Soluție corectă:
Soluție Python
n = int(input())
v = list(map(int, input().split()))

sortat = True
for i in range(n - 1):
    if v[i] > v[i + 1]:
        sortat = False

if sortat:
    print("DA")
else:
    print("NU")

Ce învățăm: folosim o variabilă sortat pe care o setăm la False imediat ce găsim o pereche în dezordine.

EXERCIȚII PRACTICE

Exercițiul Practic: Metoda bulelor

Sarcini de lucru

Aplică metoda bulelor în programe complete și observă cum evoluează lista la fiecare parcurgere.

Sarcina 1: Temperaturi sortate prin bule

Cerință: Scrie un program care citește n temperaturi (numere reale) și le sortează crescător prin metoda bulelor, apoi le afișează.

Soluție:
n = int(input())
temp = list(map(float, input().split()))

for i in range(n - 1):
    for j in range(n - 1 - i):
        if temp[j] > temp[j + 1]:
            temp[j], temp[j + 1] = temp[j + 1], temp[j]

for x in temp:
    print(x, end=" ")

Verifică: aceeași metodă funcționează și pentru numere reale, nu doar pentru întregi.

Sarcina 2: Lista după fiecare parcurgere

Cerință: Scrie un program care citește n numere, le sortează prin metoda bulelor și afișează lista după fiecare parcurgere.

Soluție:
n = int(input())
v = list(map(int, input().split()))

for i in range(n - 1):
    for j in range(n - 1 - i):
        if v[j] > v[j + 1]:
            v[j], v[j + 1] = v[j + 1], v[j]
    print(v)

Verifică: pe ecran vezi fiecare parcurgere, cu cea mai mare valoare așezată treptat la coadă.

Scrie pe caiet - De reținut

Titlul lecției

Metoda bulelor

Definiția lecției

Metoda bulelor sortează o listă comparând elementele vecine și interschimbându-le dacă sunt în ordine greșită. O parcurgere completă a listei duce cel mai mare element rămas la finalul ei, ca o bulă de aer care urcă la suprafață. După i parcurgeri, ultimele i elemente sunt fixate, deci bucla interioară merge doar până la n - 1 - i. Pentru lista [6, 2, 8, 4, 1], prima parcurgere produce 2 6 4 1 8, a doua 2 4 1 6 8, apoi 2 1 4 6 8 și, în final, 1 2 4 6 8. Dacă într-o parcurgere nu se face nicio interschimbare, lista este deja sortată, iar variabila schimbat permite oprirea devreme a algoritmului.

Definiții esențiale

Algoritmul cheie - pseudocod

pentru i = 1, n - 1 execută pentru j = 1, n - i execută dacă v[j] > v[j + 1] atunci v[j] <-> v[j + 1]

Algoritmul cheie - cod Python

Python - metoda bulelor
v = [6, 2, 8, 4, 1]
n = len(v)

for i in range(n - 1):
    for j in range(n - 1 - i):
        if v[j] > v[j + 1]:
            v[j], v[j + 1] = v[j + 1], v[j]

print(v)

Greșeli comune de evitat

Sfaturi practice și trucuri

Exemplu practic

La ora de sport, profesorul ordonează înălțimile elevilor [168, 152, 175, 160, 149] în ordine crescătoare, ca să alcătuiască echipele. Programul folosește metoda bulelor:

Python - înălțimi ordonate cu bulele
v = [168, 152, 175, 160, 149]
n = len(v)

for i in range(n - 1):
    for j in range(n - 1 - i):
        if v[j] > v[j + 1]:
            v[j], v[j + 1] = v[j + 1], v[j]

print(v)

Verifică: lista devine [149, 152, 160, 168, 175], cu cel mai înalt elev la final.