Qui presentiamo il Selection sort, detto anche algoritmo per selezione o da alcuni sel-sort, un algoritmo di ordinamento di un array, non particolarmente efficiente, ma facile da comprendere e implementare.
Questo algoritmo, chiamato anche ordinamento per minimi successivi, è importante a fini didattici, tuttavia anche se nella pratica in realtà non si usa per la sua inefficienza, non c’è programmatore che non lo conosca.
La problematica di ordinare un array è una problematica che spesso si deve affrontare, pensiamo ad esempio a fare la classifica di giocatori per punteggio, studenti per numero di assenze, candidati per numero di voti…
Seguono l’idea del funzionamento, un video di spiegazione, il codice in C++ di un’implementazione dell’algoritmo e qualche considerazione sulla complessità computazionale .
Idea del funzionamento del Selection sort
‘idea di base è semplice, si cercano successivamente i minimi dell’array.
Questo algoritmo “divide” di fatto l’array in due parti, la prima ordinata e le seconda non-ordinata, inizialmente la prima parte non conterrà alcun elemento.
L’algoritmo continuerà a cercherà il minimo tra gli elementi della parte non-ordinata e lo scambierà con il primo elemento della parte non ordinata, andando così ad aumentare di uno la dimensione della parte ordinata.
L’algoritmo termina quando la parte non-ordinata contiene un solo elemento, che sarà il massimo dell’array, e quindi l’array sarà completamente ordinato.
Video di spiegazione del selection sort
Ecco una mia breve spiegazione e implementazione in C++ dell’algoritmo selection sort.
Codice del selection sort
Qui sotto in immagine il codice in C++ del selection sort realizzato nel video, la versione eseguibile si trova al link: selection sort.
Complessità computazionale selection sort
Per chi conoscesse già cosa si intende con complessità computazionale, la complessità computazionale di questo algoritmo è O(n²).
ticoprof 