Informatică Algoritmi
Cum se sorteaza un vector folosind bubble sort?
Bubble sort este un algoritm simplu de sortare care compară elemente adiacente într-un vector și le schimbă dacă sunt în ordine greșită, repetând până când vectorul este sortat. Are complexitatea O(n²) în cazul mediu și cel mai rău, dar O(n) în cel mai bun caz (când vectorul este deja sortat). Este ușor de implementat, dar ineficient pentru vectori mari.
Pași pentru bubble sort
- 1 Parcurge vectorul Pentru fiecare element de la indexul 0 la n-2, compară elementul curent cu următorul.
- 2 Schimbă dacă e necesar Dacă elementul curent este mai mare decât următorul (pentru sortare crescătoare), schimbă-le folosind o variabilă temporară.
- 3 Repetă trecerile Repetă pașii de mai sus pentru n-1 treceri, deoarece după fiecare trecere, cel mai mare element se mută la final.
Exemplu numeric
- Vector inițial Fie vectorul [5, 3, 8, 1]. La prima trecere: compară 5 și 3 -> schimbă -> [3, 5, 8, 1]; compară 5 și 8 -> nu schimbă; compară 8 și 1 -> schimbă -> [3, 5, 1, 8].
- A doua trecere [3, 5, 1, 8]: compară 3 și 5 -> nu schimbă; compară 5 și 1 -> schimbă -> [3, 1, 5, 8]; compară 5 și 8 -> nu schimbă.
- Trecerea finală [3, 1, 5, 8]: compară 3 și 1 -> schimbă -> [1, 3, 5, 8]; restul nu schimbă. Vectorul este sortat.
Optimizări posibile
- Oprire devreme Dacă într-o trecere nu se face niciun schimb, vectorul este sortat și algoritmul se poate opri, reducând timpul în cel mai bun caz.
- Reducerea trecerilor La fiecare trecere, cel mai mare element ajunge la final, deci poți reduce numărul de comparații progresiv.
Folosește bubble sort doar pentru vectori mici sau ca exercițiu de învățare, deoarece algoritmii mai rapizi ca quicksort sunt preferați în practică.