Nello scorso articolo abbiamo trattato l’ algoritmo di ordinamento bubble sort. In questo articolo analizzeremo l’algoritmo che permette di ordinare un vettore formato da 100 numeri interi in un determinato intervallo, denominato selection sort. Ti ricordo che il linguaggio utilizzato è il C++.
N.B. Per semplicità verranno utilizzati solo numeri interi.
Algoritmo selection sort
L’algoritmo del selection sort è un algoritmo di ordinamento, partendo dal primo elemento , si ricerca quello più piccolo (o più grande) e lo si scambia con l’elemento di partenza. Dopo n-1 passi (dove “n” è la lunghezza della struttura da ordinare) di ricerca e scambio , gli elementi saranno ordinati. Risulta poco efficiente, per la sua complessità esponenziale, ma facile da implementare.
Le variabili di cui avremo bisogno saranno:
- vettore[100]: Conterrà i numeri da ordinare in ordine sparso
- num: serve per determinare la parte di vettore da ordinare (minimo = 0, massimo = lunghezza_vettore).
- i,j,minimumindex, temp: serviranno per l’ordinamento
Strategia risolutiva
- Viene Dichiarato e inizializzato un array contenente n elementi (quindi la lunghezza dell’array è n)
- Si inizializza un indice i di un ciclo che va da 0 a n-1
- Si crea un sotto ciclo che inizializza il suo indice j (ogni volta che viene chiamato) con i+1 e arriva fino a n
- Si cerca il più piccolo elemento(o più grande) dell’array
- Si scambia l’elemento più piccolo(o più grande) con l’elemento alla posizione i
- Viene incrementato l’indice i e si torna al passo tre fino alla fine del primo ciclo.
Flow Chart
Implementazione
Per questo articolo è tutto, nel prossimo articolo verrà illustrato l’algoritmo del merge sort.
Stai cercando altre guide? Allora dai uno sguardo alla nostra raccolta dedicata agli Algoritmi.
Alla prossima!
