10.2. Metoda bulelor

Metoda bulelor compară elemente aflate pe poziții consecutive. Dacă sunt în ordine greșită, le interschimbă. Repetând parcurgerile, valorile mari se deplasează spre dreapta.

O parcurgere

La sortarea crescătoare comparăm a[j] cu a[j+1]. Dacă a[j] > a[j+1], interschimbăm cele două valori. După o parcurgere completă, cea mai mare valoare din zona analizată ajunge la final.

Oprirea anticipată

Variabila schimbat pornește cu False. Dacă apare cel puțin o interschimbare, devine True. Dacă la sfârșitul unei parcurgeri rămâne False, lista era deja sortată și putem opri.

Imaginează-ți că ai persoane așezate într-un rând după înălțime. Compari fiecare două persoane vecine; dacă cea din stânga este mai înaltă decât cea din dreapta, le schimbi locurile. După o parcurgere, valoarea cea mai mare din zona analizată ajunge la dreapta. Procesul nu se oprește aici: parcurgerile se repetă atât timp cât lista nu este sortată. Cu oprire anticipată, algoritmul se poate opri când într-o parcurgere nu s-a realizat nicio interschimbare.

Varianta de bază:

a = [5, 2, 4, 1]
n = len(a)

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

print(a)

Varianta cu oprire anticipată:

a = [5, 2, 4, 1]
n = len(a)

for i in range(n - 1):
    schimbat = False
    for j in range(n - 1 - i):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
            schimbat = True
    if not schimbat:
        break

print(a)

Algoritm Bule
citește lista a și n
pentru i ← 0, n - 2 execută
    schimbat ← fals
    pentru j ← 0, n - 2 - i execută
        dacă a[j] > a[j+1] atunci
            interschimbă a[j] cu a[j+1]
            schimbat ← adevărat
        sfârșit dacă
    sfârșit pentru
    dacă schimbat = fals atunci
        oprește repetarea
    sfârșit dacă
sfârșit pentru
SFÂRȘIT ALGORITM

• Comparăm vecini, nu elemente aflate la distanță arbitrară.
• Limita buclei interioare scade deoarece ultimele elemente sunt deja fixate.
• Pentru ordonare descrescătoare condiția devine a[j] < a[j+1].
• Oprirea anticipată poate reduce mult numărul de comparații pentru liste deja sortate sau aproape sortate.
• Bulele și selecția minimului sunt diferite: bulele interschimbă vecini succesiv, selecția caută un minim și face interschimbarea după căutare.

Problemă

Sortează crescător lista [8,3,6,2,5] prin metoda bulelor și afișează lista după fiecare parcurgere.

Analiză

La fiecare parcurgere comparăm perechi consecutive. Când perechea este descrescătoare, o interschimbăm. După prima parcurgere, maximul ajunge la final.

Python

a = [8, 3, 6, 2, 5]
n = len(a)

for i in range(n - 1):
    schimbat = False
    for j in range(n - 1 - i):
        if a[j] > a[j + 1]:
            a[j], a[j + 1] = a[j + 1], a[j]
            schimbat = True
    print(a)
    if not schimbat:
        break

Urmărirea etapelor

Parcurgerea 1: [3,6,2,5,8]. Parcurgerea 2: [3,2,5,6,8]. Parcurgerea 3: [2,3,5,6,8]. Parcurgerea 4 nu mai schimbă nimic, deci algoritmul se oprește.

Testarea

Caz normal: [8,3,6,2,5]; caz-limită: [4]; caz particular: [2,2,2]; caz deja sortat: [1,2,3,4,5]; caz descrescător: [5,4,3,2,1].

Justificarea soluției

Dacă a[j] > a[j+1], interschimbarea elimină inversiunea dintre vecini. După o parcurgere, cea mai mare valoare din zona analizată ajunge la dreapta. În cazul nefavorabil timpul este O(n²), iar cu oprire anticipată cazul favorabil poate fi O(n).

1. Sortează [7,1,4,2,9] crescător prin metoda bulelor.
2. Sortează descrescător [3,8,2,6,1].
3. Afișează lista după fiecare parcurgere.
4. Adaugă oprirea anticipată.
5. Numără interschimbările realizate.

1. Determină numărul de comparații pentru n=6 în varianta fără oprire anticipată.
2. Explică de ce lista deja sortată beneficiază de oprirea anticipată.
3. Modifică algoritmul pentru a ordona numai elementele pozitive, păstrând celelalte pe pozițiile lor.
4. Aplică metoda unei liste de temperaturi pozitive și verifică ordonarea.
5. Compară selecția minimului și bulele pentru aceeași listă.