[Algoritmi di ordinamento] Selection Sort

Aleandro Prudenzano/ novembre 15, 2017/ Developing/ 0 comments

Dopo aver visto il bubble sort, quest’oggi passiamo ad un altro algoritmo – semplice sia nella comprensione che nell’attuazione – che prende il nome di selection sort.

È l’algoritmo di ordinamento array più simile a ciò che la mente umana fa per ordinare una qualsiasi sequenza: trova il minore e lo porta avanti.

Inoltre è l’algoritmo più indicato per ordinare delle sequenze di dati molto grandi (record con molti parametri, ad esempio) in quanto c’è al massimo una sola permutazione per ciclo e questo comporta meno dispendio di tempo passato a copiare dati. 

Come funziona?

Come abbiamo già detto, si tratta di trovare il minore e portarlo avanti.
Vediamo un esempio pratico usando questo array disordinato: {3,1,5,2,4}

Il minore è l’ 1, portiamolo in prima posizione ottenendo {1,3,5,2,4}.
Questo array lo possiamo intendere come diviso in due porzioni: la porzione ordinata {1} e la porzione da ordinare {3,5,2,4}.

La grandezza del primo sotto-vettore è esattamente il numero di passaggi che abbiamo già effettuato (1, appunto).
Mentre il secondo sotto-array ha inizio
nella cella con identificativo il numero di passaggi effettuati (sempre 1).

Tenendo a mente questa caratteristica dei sotto array andiamo avanti nell’ordinamento.
Il minore è ora il 2, quindi passiamo ad avere {1,2} (dimensione: 2) e {5,3,4} (cella di inizio: 2) e ripetiamo il processo fino ad avere la sequenza {1,2,3,4,5}.

Gli step essenziali di questo ordinamento sono:

  1. Trovare il minore nella porzione di array non ordinato;
  2. Permutare il minore con il primo elemento del sotto-array non ordinato;
  3. Aggiornare la variabile che tiene la posizione iniziale del sotto-vettore non ordinato e ripetere dallo step 1.

Implementazione in C

//Assumo vet[] come vettore da ordinare
//Assumo n come lunghezza del vettore

for(int i=0; i<n-1; i++){
  //Inizio ricerca del minimo del vettore
  int posMin = i;
  for(int j=i+1; j<n; j++){
    if(vet[j]<=vet[posMin])
      posMin = j;
  }
  //Fine della ricerca del minimo del vettore
  
  //Scambio del minore con il primo del sottoarray non ordinato
  if(i != posMin){
    int app = vet[posMin];
    vet[posMin] = vet[i];
    vet[i] = app;
  }
}

Spiegazione del codice

Iniziamo con un ciclo for da 0 a n-1 in quanto quando avremo il secondo sotto-array di dimensione 1 non ha senso cercare il minore.

All’interno di questo for iniziamo con la ricerca del minore inizializzando una variabile posMin (che fantasia) con la posizione della prima cella del sotto-array disordinato (i).

Iniziamo quindi a comparare ogni singola cella del sotto-vettore disordinato con la cella che ora viene puntata da posMin e lo facciamo con un secondo ciclo for, che inizializza un secondo indice (j) alla posizione subito dopo quella puntata da i (j=i+1).
Se questa cella risulta minore di quella puntata da posMin, aggiorniamo la nostra variabile che punta al minore.

Una volta finito il ciclo, in posMin si troverà il numero di cella che contiene il minore nel vettore.
Se questa cella non risulta già essere la prima del sotto-vettore disordinato possiamo procedere a farcela diventare con un semplice scambio, utilizzando una variabile d’appoggio. 

Conclusione

Per qualsiasi dubbio potete contattarci utilizzando i commenti o le nostre pagine social.

About Aleandro Prudenzano

17 anni passati tra scienza, computer, elettronica e serie tv. Ora provo a raccontare a voi un po' delle cose che ho imparato negli anni nell'attesa di impararne altre. Enjoy the culture!

Facci sapere cosa ne pensi con un commento!