Informatică Programare
Sortare rapida (quicksort) implementare C++
Sortarea rapidă (quicksort) în C++ este un algoritm de sortare care folosește strategia divide et impera. El alege un pivot și partiționează vectorul în elemente mai mici și mai mari decât pivotul. Complexitatea medie este O(n log n).
Implementare pas cu pas
- 1 Pasul 1 Alege un pivot (de exemplu, ultimul element al vectorului).
- 2 Pasul 2 Partiționează vectorul: mută elementele mai mici decât pivotul la stânga, cele mai mari la dreapta.
- 3 Pasul 3 Apelează recursiv quicksort pe subvectorii din stânga și dreapta pivotului.
Exemplu numeric
- Vector inițial [5, 2, 9, 1, 5, 6]
- Pivot 6 Partiționare: [5, 2, 1, 5] 6 [9]
- Sortare recursivă Aplică quicksort pe [5, 2, 1, 5] și [9].
Folosește pivotul median pentru a evita cazul worst-case O(n^2).