Informatică Programare
Algoritm quicksort C++
Quicksort este un algoritm de sortare eficient bazat pe principiul divide et impera, cu o complexitate medie de O(n log n). În C++, funcționează prin alegerea unui pivot din listă, împărțind lista în elemente mai mici și mai mari decât pivotul, apoi sortând recursiv cele două subliste. Este rapid și utilizat pe scară largă în practică.
Pași algoritmului quicksort
- 1 Alege pivotul Selectează un element din listă ca pivot; de obicei ultimul, primul sau unul aleatoriu.
- 2 Partiționează lista Rearanjează lista astfel încât elementele mai mici decât pivotul să fie în stânga și cele mai mari în dreapta.
- 3 Sortează recursiv Aplică quicksort recursiv pe sublista din stânga și cea din dreapta pivotului.
Exemplu de implementare C++
- Funcția partition int partition(int arr[], int low, int high) { int pivot = arr[high]; int i = low - 1; for (int j = low; j < high; j++) if (arr[j] < pivot) { i++; swap(arr[i], arr[j]); } swap(arr[i+1], arr[high]); return i+1; }
- Funcția quickSort void quickSort(int arr[], int low, int high) { if (low < high) { int pi = partition(arr, low, high); quickSort(arr, low, pi-1); quickSort(arr, pi+1, high); } }
- Utilizare int arr[] = {10, 7, 8, 9, 1, 5}; int n = 6; quickSort(arr, 0, n-1);
- Rezultat Lista sortată: {1, 5, 7, 8, 9, 10}.
Quicksort este ideal pentru sortarea rapidă a listelor mari, dar poate fi lent în cel mai rău caz (O(n²)).