Sortarea prin selecție (Selection Sort) în C++

Sortarea prin selecție (Selection Sort) în C++

Sortarea prin selecție (Selection Sort) este probabil cel mai bun algoritm de sortare în complexitate O(n2)O(n^2) datorită numărului foarte mic de interschimbări pe care le efectuează în comparație cu Bubble Sort și celelalte, dar și a constantei 1/21 / 2 din spatele acestei complexități. Vom considera că dorim să sortăm crescător vectorul vv de lungime nn indexat de la 11

Algoritm

Considerăm că primele m1m - 1 elemente din vector sunt deja pe pozițiile lor corespunzătoare (cele pe care trebuie să fie după ce sortăm vectorul). Inițial, m=1m = 1 Efectuăm de n1n - 1 ori următoarele operații: Parcurgem vectorul de la poziția mm până la nn pentru a determina minimul acestor valori, min\mathrm{min} cât și poziția lui, iMin\mathrm{iMin} La pasul mm minimul determinat este, evident, al mmlea cel mai mic număr din vector. Așadar, acesta trebuie să stea pe poziția mm Prin urmare, interschimbăm elementele v[m]v[m] și v[iMin]v[\mathrm{iMin}] Incrementăm mmul și repetăm procesul. Facem asta doar de n1n - 1 ori, pentru că după ultimul pas, mai rămâne de sortat doar ultimul element. Care nu poate fi deja decât unde trebuie.

Exemplu

Am reprezentat cu galben elementul curent, cu roșu elementul minim și cu verde elementele sortate:

Implementare în C++

Mai jos este implementarea sortării prin selecție în C++. Iterez pe mm de la 11 la n1n - 1 La fiecare pas, inițializez pe min\mathrm{min} și iMin\mathrm{iMin} în funcție de prima valoare de unde se începe căutarea minimului, v[m]v[m] Apoi, parcurg restul vectorului, de la v[m+1]v[m + 1] la v[n]v[n] pentru actualizarea minimului când este cazul. La final, interschimb valorile variabilelor v[m]v[m] și v[iMin]v[\mathrm{iMin}] folosind o variabilă auxiliară aux\mathrm{aux}

Sortarea prin selecție
for (int m = 1; m < n; m++) {
int min = v[m], iMin = m;
for (int i = m + 1; i <= n; i++)
if (v[i] < v[iMin]) {
min = v[i];
iMin = i;
}
int aux = v[m];
v[m] = v[iMin];
v[iMin] = aux;
}

Aceasta este sortarea prin selecția minimului, dar programul poate fi modificat destul de ușor pentru a efectua o sortare prin selecția maximului: Sortăm vectorul de la dreapta la stânga, calculând la fiecare pas maximul din secvența nesortată și inserându-l spre sfârșitul vectorului. De asemenea, dacă în programul de mai sus schimbăm semnul din < în >, practic vom calcula maxime în loc de minime, și astfel vom sorta vectorul descrescător.

Complexitate

În sortarea prin selecție se intră de n1n - 1 ori în primul for, iar la fiecare iterație, se efectuează nm+1n - m + 1 pași pentru aflarea minimului. Ignorăm interschimbările (swap-urile), pentru că n-ar reprezenta decât un +1+ 1 la fiecare iterație, și rezultă că în total se efectuează

n+(n1)++2=n(n+1)21n + (n - 1) + \cdots + 2 = \frac{n(n+1)}{2} - 1

pași. Asta înseamnă o complexitate de ordinul O(n2)O(n^2) Dar aici contează mult și constanta din fața ei, care este 1/21 / 2 Aceasta face sortarea prin selecție să fie cea mai rapidă metodă de sortare în complexitate O(n2)O(n^2)

Dacă aveți vreo întrebare despre sortarea prin selecție, lăsați-o mai jos într-un comentariu pentru a vă ajuta

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii