Corsi registrati su
C, C++, Python, JavaScript
Corsi in diretta per la formazione di Front End Developer e Back End Developer
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 θ (n2).
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
Somma elementi diagonale principale di una matrice
il codice è sbagliato, nel for la codizione è <= 🙂
Grazie mille, in realtà è corretto. Conviene effettuare la stampa degli elementi separatamente per vederlo.