Informatică Algoritmi
Algoritmi de sortare diferenta intre
Diferențele dintre algoritmii de sortare se referă la complexitatea timp, spațiu și tipul de date. Principalii algoritmi sunt Bubble Sort, Selection Sort, Insertion Sort, Merge Sort și Quick Sort.
Complexitate și eficiență
- Bubble Sort Complexitate O(n²) în cazul mediu și cel mai rău, O(n) în cel mai bun (dacă e sortat). Sortare prin comparare vecinilor, ineficient pentru liste mari.
- Selection Sort Complexitate O(n²) în toate cazurile. Găsește elementul minim și îl plasează la poziția corectă, mai rapid decât Bubble Sort în practică dar tot O(n²).
- Insertion Sort Complexitate O(n²) în mediu și cel mai rău, O(n) în cel mai bun. Bun pentru liste mici sau parțial sortate, inserează elemente în poziția corectă.
Algoritmi avansați
- Merge Sort Complexitate O(n log n) în toate cazurile, dar necesită spațiu suplimentar O(n). Folosește divide et impera, stabil și bun pentru liste mari.
- Quick Sort Complexitate medie O(n log n), cel mai rău O(n²) dacă pivotul e prost ales. Folosește pivot, eficient în practică, dar nu stabil.
- Exemplu numeric Pentru lista [5,3,8,1], Bubble Sort face 3 treceri, Selection Sort găsește minimul 1, Insertion Sort inserează 3 după 5.
Alege algoritmul în funcție de mărimea datelor: Merge Sort pentru liste mari, Insertion Sort pentru liste mici.