Algoritmi de sortare: metoda bulelor (bubble sort), sortare prin selectie

Sortarea este procesul prin care elementele unui vector (sir de numere, cuvinte etc.) sunt aranjate intr-o ordine specifica, de obicei crescatoare sau descrescatoare. In aceasta lectie, vom studia doi algoritmi simpli, dar foarte utili pentru intelegerea principiilor de baza ale sortarii: metoda bulelor (Bubble Sort) si sortarea prin selectie (Selection Sort).

Metoda bulelor: Algoritmul 'bulelor' functioneaza prin parcurgerea repetata a vectorului si compararea perechilor de elemente adiacente. Daca ordinea este gresita (de exemplu, intr-o sortare crescatoare, primul element este mai mare decat al doilea), acestea se schimba intre ele. Dupa fiecare parcurgere completa, cel mai mare element 'pluteste' la sfarsitul vectorului, ca o bulica de aer intr-un pahar cu apa.

Algoritmul continua parcurgerile, ignorand ultimele elemente deja sortate, pana cand nu se mai efectueaza nicio interschimbare. Complexitatea sa este O(n^2) in cazul cel mai defavorabil, ceea ce il face ineficient pentru vectori mari, dar este usor de implementat si intelegut.

Sortarea prin selectie: Acest algoritm selecteaza la fiecare pas elementul minim (sau maxim) dintr-o portiune nesortata a vectorului si il plaseaza la inceputul acelei portiuni. Mai exact, se cauta cel mai mic element intre pozitia curenta i si sfarsitul vectorului, apoi se interschimba cu elementul de pe pozitia i. Astfel, dupa fiecare pas, vectorul se imparte in doua zone: o zona sortata la stanga si una nesortata la dreapta.

Complexitatea este tot O(n^2), dar algoritmul face mai putine interschimbari decat metoda bulelor (maxim n-1). Este mai eficient in practica pentru seturi mici de date, dar la fel de simplu de inteles.

Diferenta principala: In bubble sort, interschimbarile sunt frecvente si se fac intre elemente adiacente, in timp ce in selection sort, interschimbarea are loc doar o data pe pas, dupa ce s-a gasit minimul. Ambii algoritmi sunt stabili? Bubble sort poate fi stabil, dar selection sort nu este stabil in varianta clasica (poate schimba ordinea relativa a elementelor egale).

Pentru invatare, ei sunt fundatia pentru algoritmi mai avansati, cum ar fi quicksort sau mergesort.

Vom ilustra ambii algoritmi cu exemple concrete, pas cu pas, pentru a intelege cum se schimba elementele si cum se ajunge la vectorul sortat.

Exemple

• Exemplul 1 (Bubble Sort): Sa sortam vectorul [5, 3, 8, 4, 2] crescator. Pasul 1: comparam 5 si 3, 5>3, interschimbam => [3,5,8,4,2]; comparam 5 si 8, nu interschimbam; comparam 8 si 4, 8>4, interschimbam => [3,5,4,8,2]; comparam 8 si 2, 8>2, interschimbam => [3,5,4,2,8]. Dupa primul pas, 8 este la final. Pasul 2: comparam 3 si 5, nu; 5 si 4, 5>4, interschimbam => [3,4,5,2,8]; 5 si 2, 5>2, interschimbam => [3,4,2,5,8]; nu mai comparam cu ultimul. Pasul 3: comparam 3 si 4, nu; 4 si 2, 4>2, interschimbam => [3,2,4,5,8]. Pasul 4: comparam 3 si 2, 3>2, interschimbam => [2,3,4,5,8]. Vectorul este sortat.
• Exemplul 2 (Selection Sort): Acelasi vector [5, 3, 8, 4, 2]. Pasul 1: cautam minimul intre pozitiile 0-4. Minimul este 2 (pozitia 4). Interschimbam 5 cu 2 => [2, 3, 8, 4, 5]. Acum primele elemente (2) sunt sortate. Pasul 2: cautam minimul intre pozitiile 1-4. Minimul este 3 (pozitia 1). Nu e nevoie de interschimbare (deja pe loc). Vectorul ramane [2,3,8,4,5]. Pasul 3: minim intre pozitiile 2-4. Minimul este 4 (pozitia 3). Interschimbam 8 cu 4 => [2,3,4,8,5]. Pasul 4: minim intre pozitiile 3-4. Minimul este 5 (pozitia 4). Interschimbam 8 cu 5 => [2,3,4,5,8]. Sortare completa.
• Exemplul 3 (Comparatie performanta): Daca vectorul este deja sortat, Bubble Sort poate detecta (cu un flag) ca nu s-a facut nicio interschimbare si se opreste dupa primul pas, avand complexitate O(n). Selection Sort va parcurge totusi toate elementele, fara a face interschimbari inutiile, dar va cauta minimul de n-1 ori, avand tot O(n^2). De exemplu, pentru [1,2,3,4,5], Bubble Sort face un singur pas (4 comparatii, 0 interschimbari), iar Selection Sort face 4 pasi (10 comparatii, dar 0 interschimbari).

Concepte cheie: Sortare crescatoare/descrescatoare, Interschimbare (swap), Compararea perechilor adiacente (bubble), Selectarea minimului (selection), Vector partial sortat, Complexitatea O(n^2), Stabilitatea unui algoritm de sortare