Bun, hai să vorbim despre unul dintre cele mai importante și fundamentale subiecte din algoritmică: METODELE DE ORDONARE (SORTARE). Nu e doar despre aranjare (cuvânt plictisitor) și organizare. E despre cum transformi o grămadă dezordonată de date într-o listă perfect organizată, ca să poți căută rapid, analiza ușor și înțelege mai bine informațiile.
1. De ce Să Sortăm? “Căutarea Într-o Agendă”
Gândește-te la sortare ca la aranjarea unei agende telefonice în ordine alfabetică:
- Fără sortare: Cauți “Popescu” → verifici toate numele una câte una
- Cu sortare: Cauți “Popescu” → mergi direct la litera P
4 motive principale pentru sortare:
- Căutare rapidă – poți folosi căutarea binară
- Date mai lizibile – vezi imediat min, max, mediană
- Pregătește pentru alte operații – unirea a doi vectori sortați e ușoară
- E necesară pentru multe algoritme – statistici, grafice, baze de date
2. Bubble Sort (Sortarea Bulelor): “Cel Mai Simplu”
Cum funcționează: Compară două elemente vecine, le schimbă dacă sunt în ordine greșită, repetă până când tot vectorul e sortat. Ca bulele care urcă în suprafața apei.
#include <iostream>
using namespace std;
int main() {
int v[] = {5, 2, 8, 1, 3};
int n = 5;
cout << "Vector nesortat: ";
for(int i = 0; i < n; i++) cout << v[i] << " ";
cout << endl;
// Bubble Sort
for(int i = 0; i < n-1; i++) {
for(int j = 0; j < n-i-1; j++) {
if(v[j] > v[j+1]) {
// Schimbă elementele
int temp = v[j];
v[j] = v[j+1];
v[j+1] = temp;
}
}
}
cout << "Vector sortat (Bubble Sort): ";
for(int i = 0; i < n; i++) cout << v[i] << " ";
return 0;
}Ce se întâmplă pas cu pas:
5 2 8 1 3 → 2 5 1 3 8 → 2 1 3 5 8 → 1 2 3 5 8Optimizare: Dacă într-o trecere nu se face niciun schimb, vectorul e deja sortat.
Complexitate: O(n²) în cel mai rău caz
Când să folosești: Pentru vectori mici sau aproape sortați
3. Selection Sort (Sortarea prin Selecție): “Găsește Minimul”
Cum funcționează: Găsește cel mai mic element, îl pune pe prima poziție. Apoi găsește următorul cel mai mic din rest, îl pune pe a doua poziție, etc.
#include <iostream>
using namespace std;
int main() {
int v[] = {5, 2, 8, 1, 3};
int n = 5;
cout << "Vector nesortat: ";
for(int i = 0; i < n; i++) cout << v[i] << " ";
cout << endl;
// Selection Sort
for(int i = 0; i < n-1; i++) {
// Găsește poziția minimului în partea nesortată
int pozitieMin = i;
for(int j = i+1; j < n; j++) {
if(v[j] < v[pozitieMin]) {
pozitieMin = j;
}
}
// Schimbă elementul minim cu primul din partea nesortată
if(pozitieMin != i) {
int temp = v[i];
v[i] = v[pozitieMin];
v[pozitieMin] = temp;
}
}
cout << "Vector sortat (Selection Sort): ";
for(int i = 0; i < n; i++) cout << v[i] << " ";
return 0;
}Ce se întâmplă pas cu pas:
5 2 8 1 3 → 1 2 8 5 3 → 1 2 8 5 3 → 1 2 3 5 8 → 1 2 3 5 8Complexitate: O(n²) întotdeauna (face aceeași număr de comparări indiferent dacă e sortat sau nu)
Când să folosești: Când vrei putine schimbări (face doar n-1 schimbări)
4. Insertion Sort (Sortarea prin Inserție): “Ca Să Înșurubezi”
Cum funcționează: Luați un element, inserați-l în poziția corectă în partea deja sortată. Ca și cum ai sorta cărți de joc în mână.
#include <iostream>
using namespace std;
int main() {
int v[] = {5, 2, 8, 1, 3};
int n = 5;
cout << "Vector nesortat: ";
for(int i = 0; i < n; i++) cout << v[i] << " ";
cout << endl;
// Insertion Sort
for(int i = 1; i < n; i++) {
int elementCurent = v[i];
int j = i - 1;
// Mută elementele mai mari decât elementCurent cu o poziție la dreapta
while(j >= 0 && v[j] > elementCurent) {
v[j+1] = v[j];
j--;
}
// Inserează elementCurent în poziția corectă
v[j+1] = elementCurent;
}
cout << "Vector sortat (Insertion Sort): ";
for(int i = 0; i < n; i++) cout << v[i] << " ";
return 0;
}Ce se întâmplă pas cu pas:
5|2 8 1 3 → 2 5|8 1 3 → 2 5 8|1 3 → 1 2 5 8|3 → 1 2 3 5 8Complexitate: O(n²) în cel mai rău caz, O(n) dacă vectorul e aproape sortat
Când să folosești: Pentru vectori mici sau aproape sortați
5. Counting Sort (Sortarea prin Numărare): “Cel Mai Rapid” pentru numere mici
Cum funcționează: Numără de câte ori apare fiecare valoare, apoi reconstruiește vectorul sortat.
#include <iostream>
using namespace std;
int main() {
int v[] = {4, 2, 2, 8, 3, 3, 1};
int n = 7;
cout << "Vector nesortat: ";
for(int i = 0; i < n; i++) cout << v[i] << " ";
cout << endl;
// Găsește valoarea maximă
int max = v[0];
for(int i = 1; i < n; i++) {
if(v[i] > max) max = v[i];
}
// Vector de frecvență
int frecventa[max+1] = {0};
// Numără fiecare element
for(int i = 0; i < n; i++) {
frecventa[v[i]]++;
}
// Reconstruiește vectorul sortat
int index = 0;
for(int i = 0; i <= max; i++) {
while(frecventa[i] > 0) {
v[index] = i;
index++;
frecventa[i]--;
}
}
cout << "Vector sortat (Counting Sort): ";
for(int i = 0; i < n; i++) cout << v[i] << " ";
return 0;
}Ce se întâmplă:
Numără: 1 apare 1 dată, 2 apare de 2 ori, 3 apare de 2 ori, 4 apare 1 dată, 8 apare 1 dată
Reconstruiește: 1 2 2 3 3 4 8Complexitate: O(n + k) unde k este valoarea maximă
Când să folosești: Când ai numere întregi într-un interval mic
6. Compararea Metodelor
#include <iostream>
using namespace std;
int main() {
cout << "=== COMPARATIE METODE DE SORTARE ===\n\n";
cout << "BUBBLE SORT:\n";
cout << "- Complexitate: O(n²) in cel mai rau caz\n";
cout << "- Când: vectori mici sau aproape sortati\n";
cout << "- Avantaje: simplu de inteles\n";
cout << "- Dezavantaje: foarte lent pentru vectori mari\n\n";
cout << "SELECTION SORT:\n";
cout << "- Complexitate: O(n²) intotdeauna\n";
cout << "- Când: cand vrei putine schimbari\n";
cout << "- Avantaje: face doar n-1 schimburi\n";
cout << "- Dezavantaje: tot O(n²) comparatii\n\n";
cout << "INSERTION SORT:\n";
cout << "- Complexitate: O(n²) in cel mai rau caz, O(n) daca e aproape sortat\n";
cout << "- Când: vectori mici sau aproape sortati\n";
cout << "- Avantaje: bun pentru date care vin in flux\n";
cout << "- Dezavantaje: lent pentru vectori invers sortati\n\n";
cout << "COUNTING SORT:\n";
cout << "- Complexitate: O(n + k) unde k e valoarea maxima\n";
cout << "- Când: numere intregi intr-un interval mic\n";
cout << "- Avantaje: cel mai rapid in conditii ideale\n";
cout << "- Dezavantaje: foloseste memorie extra\n";
return 0;
}7. Sortare Descrescătoare: “Doar Schimbi Semnul”
Pentru orice algoritm, schimbă > cu < pentru a sorta descrescător!
#include <iostream>
using namespace std;
int main() {
int v[] = {5, 2, 8, 1, 3};
int n = 5;
// Bubble Sort descrescator
for(int i = 0; i < n-1; i++) {
for(int j = 0; j < n-i-1; j++) {
if(v[j] < v[j+1]) { // < in loc de >
int temp = v[j];
v[j] = v[j+1];
v[j+1] = temp;
}
}
}
cout << "Sortat descrescator: ";
for(int i = 0; i < n; i++) cout << v[i] << " ";
return 0;
}8. Implementare cu Funcții
#include <iostream>
using namespace std;
// Bubble Sort
void bubbleSort(int v[], int n) {
for(int i = 0; i < n-1; i++) {
for(int j = 0; j < n-i-1; j++) {
if(v[j] > v[j+1]) {
int temp = v[j];
v[j] = v[j+1];
v[j+1] = temp;
}
}
}
}
// Selection Sort
void selectionSort(int v[], int n) {
for(int i = 0; i < n-1; i++) {
int minIdx = i;
for(int j = i+1; j < n; j++) {
if(v[j] < v[minIdx]) minIdx = j;
}
if(minIdx != i) {
int temp = v[i];
v[i] = v[minIdx];
v[minIdx] = temp;
}
}
}
// Insertion Sort
void insertionSort(int v[], int n) {
for(int i = 1; i < n; i++) {
int key = v[i];
int j = i-1;
while(j >= 0 && v[j] > key) {
v[j+1] = v[j];
j--;
}
v[j+1] = key;
}
}
int main() {
int v[] = {5, 2, 8, 1, 3};
int n = 5;
// Alege algoritmul
bubbleSort(v, n); // Schimbă cu selectionSort sau insertionSort
cout << "Sortat: ";
for(int i = 0; i < n; i++) cout << v[i] << " ";
return 0;
}9. Testarea Corectitudinii
#include <iostream>
using namespace std;
bool esteSortat(int v[], int n) {
for(int i = 0; i < n-1; i++) {
if(v[i] > v[i+1]) {
return false; // Vectorul nu e sortat
}
}
return true; // Vectorul e sortat
}
int main() {
int v[] = {1, 2, 3, 4, 5};
int n = 5;
if(esteSortat(v, n)) {
cout << "Vectorul este sortat corect!" << endl;
} else {
cout << "Vectorul NU este sortat corect!" << endl;
}
return 0;
}10. Exerciții Practice
Exercițiul 1: Completează Bubble Sort
int v[] = {4, 1, 3, 2};
int n = 4;
for(int i = 0; i < n-1; i++) {
for(int j = 0; j < n-i-1; j++) {
if(/* condiție */) {
int temp = v[j];
v[j] = v[j+1];
v[j+1] = /* ce pui aici? */;
}
}
}Soluție:
if(v[j] > v[j+1]) {
// ...
v[j+1] = temp;
}Exercițiul 2: Ce face acest cod?
for(int i = 0; i < n-1; i++) {
int minIdx = i;
for(int j = i+1; j < n; j++) {
if(v[j] < v[minIdx]) minIdx = j;
}
int temp = v[i];
v[i] = v[minIdx];
v[minIdx] = temp;
}Răspuns: Este algoritmul Selection Sort.
Exercițiul 3: Sortează doar numerele pare
#include <iostream>
using namespace std;
int main() {
int v[] = {5, 2, 8, 1, 6, 3};
int n = 6;
// Bubble Sort doar pentru elementele pare
for(int i = 0; i < n-1; i++) {
for(int j = 0; j < n-i-1; j++) {
// Sortează doar dacă ambele sunt pare
if(v[j] % 2 == 0 && v[j+1] % 2 == 0 && v[j] > v[j+1]) {
int temp = v[j];
v[j] = v[j+1];
v[j+1] = temp;
}
}
}
cout << "Numerele pare sortate: ";
for(int i = 0; i < n; i++) {
if(v[i] % 2 == 0) cout << v[i] << " ";
}
return 0;
}În concluzie:
- Bubble Sort = cel mai simplu (compară vecinii)
- Selection Sort = găsește minimul și îl pune la început
- Insertion Sort = inserează fiecare element în poziția corectă
- Counting Sort = cel mai rapid pentru numere într-un interval mic
Regula de aur: Alege algoritmul în funcție de datele tale:
- Vector mic sau aproape sortat → Bubble, Selection, Insertion
- Numere întregi într-un interval mic → Counting Sort
- Vector mare → algoritmi mai avansați (Quick Sort, Merge Sort)
Leave a Reply