Informatică Programare
Algoritmi de sortare C++ exemple
Algoritmii de sortare în C++ sunt procedee care rearanjează elementele unei colecții într-o ordine specifică, de obicei crescătoare. În C++, cei mai utilizați algoritmi sunt bubble sort, selection sort, insertion sort, merge sort și quicksort. Fiecare are o complexitate diferită și este potrivit pentru anumite tipuri de date.
Tipuri comune de algoritmi de sortare
- Bubble Sort Compară elemente adiacente și le schimbă dacă sunt în ordine greșită, repetând până când lista este sortată. Complexitate: O(n²).
- Selection Sort Găsește elementul minim din listă și îl plasează la început, repetând pentru restul listei. Complexitate: O(n²).
- Insertion Sort Construiește lista sortată un element pe rând, inserând fiecare element în poziția corectă. Complexitate: O(n²).
- Merge Sort Împarte lista în jumătăți, sortează recursiv fiecare jumătate și apoi le îmbină. Complexitate: O(n log n).
- Quicksort Alege un pivot, împarte lista în elemente mai mici și mai mari decât pivotul, apoi sortează recursiv părțile. Complexitate medie: O(n log n).
Exemplu simplu: Bubble Sort în C++
- 1 Declară vectorul int arr[] = {64, 34, 25, 12, 22, 11, 90}; int n = sizeof(arr)/sizeof(arr[0]);
- 2 Implementează bubble sort for (int i = 0; i < n-1; i++) for (int j = 0; j < n-i-1; j++) if (arr[j] > arr[j+1]) swap(arr[j], arr[j+1]);
- 3 Afișează rezultatul for (int i = 0; i < n; i++) cout << arr[i] << " "; // Output: 11 12 22 25 34 64 90
Pentru liste mici, folosește bubble sort sau insertion sort; pentru liste mari, merge sort sau quicksort.