Tra gli algoritmi di Ordinamento. Il Selection Sort è uno dei più semplici da apprendere. Ma non il più efficiente.

La complessità computazionale di questo algoritmo di ordinamento è O(n^2).
Qui di seguito l’implementazione di tale algoritmo sotto forma di funzione che riceve in entrata l’array da ordinare e il numero di elementi dell’array.

/*
SELECTION SORT
 
Ricerca il minimo nella parte di array non ancora ordinata e lo ordina. Poi prosegue con altre ricerche ripetute
nella parte di array non ancora ordinata.
 
Complessità computazionale: O(n^2)
 
pag. 524
*/
 
void selection_sort(int a[], int n){ //funzione tipo void, effettua modifiche permanenti e non restituisce nulla.
int min = a[0], i = 0, j, p = 0; //dichiariamo il minimo dell'array uguale alla sua prima componente.
 
while (i < n) { //scansioniamo tutto l'array
 
  for (j = i; j < n; j++){ //scansiona tutto l'array partendo da una posizione in più poichè uscendo da qua 1 elemento sarà già ordinato.
 
  if (a[j] < min) { //se l'elemento attuale è minore del minimo allora l'elemento attuale sarà il nuovo minimo
                 min = a[j]; 
                 p = j; //memorizziamo la posizione del minimo nell'array
                  }
                         }
 
scambia (&a[i],&a[p]);//uscendo dal ciclo for scambiamo di posizione l'elemento iniziale della scansione con il minimo trovato.
i++;//incrementiamo i per passare a scansionare il restante array non ancora ordinato.
min = a[i]; //settiamo il minimo uguale all'elemento dopo.
 
              }
}

Algoritmo Selection Sort in C


Per qualsiasi chiarimento o dubbio commentate.