SORTARE PRIN SELECȚIE

Ideea algoritmului este urmatoarea: tabloul unidimensional (vectorul) este împărţit în două părţi imaginare – o parte sortată şi o parte nesortată. La început, partea sortată este goală, în timp ce partea nesortată conţine întreg tabloul. La fiecare pas, algoritmul găseşte elementul minim din partea nesortată şi îl adaugă la finalul părţii sortate. Când partea nesortată rămâne goală, algoritmul se opreşte.

Când algoritmul sortează un tablou unidimensional, interschimbă primul element al părţii nesortate cu elementul minim şi după aceea el este inclus în partea sortată. Această implementare a sortării prin selecţie nu este stabilă. În cazul când sortăm o listă, şi, în loc de interschimbări, elementul minim este legat de partea nesortată, sortarea prin selecţie este stabilă.

Exemplu

Dorim să sortăm şirul {5, 1, 9, -2, 14, 2, 9,} utilizând sortarea prin selecţie.

Pașii în execuția algoritmului sunt:

5, 1, 9, -2, 14, 2, 9; nesortat

5, 1, 9, -2, 14, 2, 9; interschimbăm 5 cu -2

-2, 1, 9, 5, 14, 2, 9; 1 rămâne pe poziţie

-2, 1, 9, 5, 14, 2, 9; interschimbăm 2 cu 9

-2, 1, 2, 5, 14, 9, 9; 5 ramâne pe poziţie

-2, 1, 2, 5, 14, 9, 9; interschimbăm 14 cu 9

-2, 1, 2, 5, 9, 9 14; vector sortat

Algoritm descris în pseudocod

pentru i ← 0,n-1 execută

min ← i ;

pentru j ← i+1,n execută

dacă v[j]<v[i] atunci

min ← j ;

sfdacă

sfpentru

dacă min ≠ i atunci

aux ← v[i] ;

v[i] ← v[min] ;

v[min] ← aux ;

sfdacă

sfpentru

Implementare C++

void sortareSelecţie(int v[], int n)

{

int i, j, min, aux;

for (i = 0; i < n - 1; i++)

{

min = i;

for (j = i + 1; j < n; j++)

if (v[j] < v[min])

min = j;

if (min != i)

{

aux = v[i];

v[i] = v[min];

v[min] = aux;

}

}

}