Algoritmo di ordinamento Selection sort in C

Il selection sort, detto anche ordinamento per selezione, è un algoritmo di ordinamento comparativo di tipo in-place, in grado di ordinare un array selezionando il valore minore dalla sequenza di partenza e spostandolo nella sequenza ordinata.

In particolare l’algoritmo suddivide l’array in due sottoparti, una parte ordinata che inizia da sinistra e si espande verso destra, e la parte restante che contiene tutti gli altri elementi non ordinati dell’array. Di conseguenza, la prima sottoparte (quella ordinata) sarà inizialmente vuota, mentre la seconda sottoparte conterrà tutti i valori dell’array. 

L’algoritmo procede selezionando l’elemento più piccolo (o più grande, in caso di ordinamento decrescente) partendo dall’inizio della sottoparte non ordinata e, una volta passati tutti gli elementi, sposta il numero trovato nella sottoparte ordinata dell’array. In questo modo, ad ogni iterazione dell’algoritmo, l’array risulterà sempre più ordinato.

Fonte gif: Wikipedia

Chiaramente il fatto di dover confrontare un elemento con tutti gli altri elementi contenuti nell’array, rende l’algoritmo estremamente inefficiente soprattutto con array di dimensioni elevate. 

Nota: è importante ricordare che l’algoritmo è di tipo in place, ovvero non crea nuove strutture dati, ma crea dei sottoinsiemi (in un certo senso, virtuali) all’interno dell’array iniziale.

Esempio applicazione algoritmo di selection sort

Consideriamo la seguente lista di numeri L = (5, 2, 6, 3) e applichiamo l’algoritmo di ordinamento selection sort passo per passo. Per visualizzare in maniera più chiara i singoli passaggi dell’algoritmo useremo due liste, la prima conterrà gli elementi ordinati, mentre la seconda conterrà tutti gli altri elementi dell’array.

Inizialmente gli elementi ordinati sono 0, di conseguenza le due liste saranno definite nella seguente maniera:

() (5, 2, 6, 3) 

con numero minimo 2, che verrà spostato nella sottoparte a sinistra:

(2) (5, 6, 3) 

Questo procedimento continua fino a che non rimane alcun elemento nella lista di destra:

(2, 3) (5, 6) 

(2, 3, 5) (6) 

(2, 3, 5, 6) () 

Prestazioni algoritmo selection sort

Come già accennato precedentemente, l’algoritmo risulta essere estremamente inefficiente quando viene applicato a liste di dimensioni elevate, performando in maniera peggiore di altri tipi di algoritmo di ordinamento quali l’insertion sort, a cui somiglia molto. In particolare l’algoritmo è di tipo adattivo, ovvero il suo tempo di esecuzione dipende dalla dimensione dell’input.

Dato che l’algoritmo deve confrontare ogni elemento con tutti gli altri elementi dell’array, presenta una complessità di tipo quadratica O(n²).

Implementazione algoritmo selection sort in C

Di seguito viene riportata l’implementazione dell’algoritmo di ordinamento selection sort in C.

Per poter implementare in maniera corretta l’algoritmo abbiamo bisogno di utilizzare due cicli for, il primo per scorrere ogni singolo elemento, il secondo per verificare se l’attuale elemento che si trova in posizione i sia il più piccolo tra tutti gli altri dell’array.

Specificamente, se uno dei valori successivi risulta essere più piccolo del valore attuale che si trova in posizione i, la variabile indice_min viene aggiornata con l’indice della posizione del nuovo valore e al termine del secondo ciclo il numero che si trova in posizione i viene sostituito con il numero che si trova in posizione indice_min. In questo modo, al termine del primo ciclo for, l’intero array risulta essere completamente ordinato.

#include <stdio.h>
#define N 10

int main() {
   int lista[10] = {6, 2, 4, 7, 5, 1, 9, 3, 15, 22};
   int indice_min, temp;

    for(int i = 0; i < N - 1; i++){
        indice_min = i;
        for(int j = i + 1; j < N; j++){
            if(lista[j] < lista[indice_min])
                indice_min = j;
        }

        temp = lista[indice_min];
        lista[indice_min] = lista[i];
        lista[i] = temp;  
    }

   for(int i = 0; i < N; i++){
        printf("%d ", lista[i]);        
   }    
}

// Output: 1 2 3 4 5 6 7 9 15 22