Algoritmi in pillole C: ordinamento con selection sort

Selection sort animata da wikipedia

Se l'ordine desiderato è quello crescente,  l'algoritmo "seleziona" il valore più piccolo dell‟array di n elementi e lo scambia con quello al primo posto. Successivamente, "seleziona" il più piccolo tra gli n-1 elementi rimasti e lo scambia con quello al secondo posto, e così via fino a che non rimane un solo elemento, l'ultimo e il più grande. 

pseudocodice:

"per i che varia da 1 a  N   per j che varia da i+1 a N       se l'elemento j è minore dell'elemento i allora          scambia i con j"

Codice:

void selectionsort(int v[], int n){
 int i,j,min,temp;
 for (i=0;i<n-1;i++) {
   min=i;
   for (j=i+1;j<n;j++)
     if (v[j]<v[min]) min=j;
   temp=v[i];
   v[i]=v[min];
   v[min]=temp;
 }
}

La complessità computazionale asintotica è O(n^2).
Caso peggiore: array ordinato in senso inverso - T. esec. prop. a n^2
Caso migliore: array già ordinato                     - T. esec. prop. a n^2