Selection sort in C

Oggi ci occuperemo dello sviluppo dell’algoritmo selection sort in C.

Il selection sort è un algoritmo di ordinamento che in questo blog affronteremo con vari linguaggi di programmazione, ma in questo articolo lo svilupperemo in linguaggio C.

Il tempo di esecuzione di questo algoritmo di ordinamento non dipende dall’input, bensì dalla dimensione dell’array, dunque si dice che è non adattivo.

L’algoritmo di volta in volta seleziona il numero minore della sequenza e lo sposta nella sequenza ordinata.

Di fatto a mano a mano avremo una sequenza ordinata a partire da sinistra.

Per realizzare l’algoritmo selection sort in C si considera allora l’indice i che va dalla posizione 0 dell’array fino ad arrivare a N-2 (consideriamo un vettore di dimensione N) e un altro indice j che va da i+1 fino ad arrivare a N-1.
Quindi si trova l’elemento più piccolo dell’array e si scambia con l’elemento alla posizione i, dopo incrementa l’indice di uno e si ritorna al passo precedente.

Servirà quindi una variabile per poter effettuare lo scambio.

Difatti quando si trova l’elemento più piccolo dell’array si scambia con l’elemento alla posizione i:

t = a[min];

a[min] = a[i];

a[i] = t;

La variabile t dunque rappresenta la variabile temporanea.

Esempio di algoritmo selection sort in C

Vediamo adesso il codice completo dell’algoritmo di ordinamento in linguaggio C:

#include <stdio.h> 


int main() { 
   int a[10] = {5,8,0,1,4,2,4,3,9,7}; 
   int i, j, min, t;

//t è la variabile temporanea utilizzata per lo scambio 

   for(i=0; i<9; i++){ 
      min=i; 
      for (j = i+1;j < 10; j++){ 
         if (a[j]<a[min]) 
            min=j; 
      } 
      t = a[min];
//si trova l'elemento più piccolo dell'array e si scambia con l'elemento alla posizione i 
      a[min] = a[i]; 
      a[i] = t;  
    }

   for(i=0; i<10; i++){
      printf("%d ", a[i]);		
   }	
}

Prestazioni del selection sort

Vediamo adesso le prestazioni dell’algoritmo selection sort.

L’ordinamento per selezione effettua N ( N − 1 ) / 2 confronti, dunque la complessità di tale algoritmo è dell’ordine di θ (n²). 

L’algoritmo in effetti risulta poco efficiente, per la sua complessità esponenziale, ma è piuttosto facile da implementare. 

Conclusioni

In questa lezione abbiamo affrontato l’algoritmo di ordinamento selection sort in C, nella prossima lezione affronteremo anche altri algoritmi di ordinamento.

Alcuni link utili

Indice tutorial linguaggio C

Array o vettori

Quick sort in linguaggio C

Merge sort in linguaggio C

Insertion Sort in lingaggio C

Somma elementi diagonale principale di una matrice

Esercizio con le matrici in C

Triangolo di Tartaglia in C