Algoritmo di ordinamento, Selection Sort in C.

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.

              }
}