Sortarea prin selecție (Selection Sort) se bazează pe următoarea idee:
- fie un vector
X[]
cun
elemente; - plasăm în
X[0]
cea mai mică valoare din vector; - plasăm în
X[1]
cea mai mică valoare rămasă; - etc.
O descriere a algoritmului este:
- parcurgem vectorul cu indicele
i
- parcurgem cu indicele
j
elementele din dreapta luiX[i]
- dacă elementele
X[i]
șiX[j]
nu sunt în ordinea dorită, le interschimbăm
- dacă elementele
- parcurgem cu indicele
Observații
- în algoritmul de mai sus, pentru fiecare valoare a lui
i
, înX[i]
se obține cea mai mică (mare) valoare dintre elementele cu indicii, i+1, ..., n
; altfel spus, pentru fiecarei
, înX[i]
se selectează minimul (maximul) dintre elementelei, i+1, ..., n
. - metoda se mai numește sortare prin selecție directă, sortare prin selecție implicită sau sortare prin interschimbare.
Exemplu
Să ordonăm următorul vector, în care n=5
:
i = 0 |
i = 1 |
i = 2 |
i = 3 |
La final |
Secvență C++
int n, X[100]; //citire X[] cu n elemente for(int i = 0 ; i < n - 1 ; i ++) for(int j = i + 1 ; j < n ; j ++) if(X[i] > X[j]) { int aux = X[i]; X[i] = X[j]; X[j] = aux; }
Algoritmul descris mai sus se mai numește sortare prin selecție generală, sau implicită. O altă variantă este următoarea, în care pentru fiecare secvență i ... n-1
se determină explicit minimul și se interschimbă cu X[i]
.
int n, X[100]; //citire X[] cu n elemente for(int i = 0 ; i < n - 1 ; i ++) { int p = i; for(int j = i + 1 ; j < n ; j ++) if(X[j] < X[p]) p= j; int aux = X[i]; X[i] = X[p]; X[p] = aux; }
Animație
Resurse online
Animație, valori configurabile
Animație, mai multe metode de sortare
Un filmuleț care ilustrează “Sortarea prin selecție”, creat la Târgu Mureș: