Selection sort in C

In questa lezione ci concentreremo sullo sviluppo dell’algoritmo di selection sort in linguaggio C, un metodo di ordinamento ampiamente utilizzato nella pratica della programmazione. Il selection sort è noto per la sua semplicità concettuale e la relativa facilità di implementazione, rendendolo un punto di partenza ideale per comprendere i concetti fondamentali degli algoritmi di ordinamento.

L’obiettivo principale del selection sort è quello di organizzare gli elementi di un array in ordine crescente (o decrescente). A differenza di alcuni altri algoritmi di ordinamento, come ad esempio il quicksort o il mergesort, il selection sort non si adatta all’input e il tempo di esecuzione dipende solo dalla dimensione dell’array. Questo lo rende non adattivo, ma allo stesso tempo lo rende relativamente prevedibile e facile da analizzare.

Il cuore del selection sort consiste nel selezionare ripetutamente l’elemento più piccolo dall’array e spostarlo nella posizione corretta nella parte già ordinata dell’array. Questo processo continua finché tutti gli elementi non sono stati inseriti nella sequenza ordinata. Quindi, a mano a mano che procediamo con l’algoritmo, otteniamo una sequenza ordinata che si estende da sinistra a destra.

Per implementare questo algoritmo in C, utilizziamo due indici: i, che scorre dall’inizio dell’array fino a N − 2, e j, che parte da i + 1 e va fino a N − 1, dove N è la dimensione dell’array. Iteriamo attraverso l’array e, ad ogni passaggio, troviamo l’indice dell’elemento più piccolo nella parte non ordinata dell’array. Successivamente, scambiamo questo elemento con l’elemento nella posizione corrente i. Questo processo continua fino a quando non abbiamo inserito tutti gli elementi nella sequenza ordinata.

Una parte cruciale dell’algoritmo è la necessità di una variabile temporanea t per consentire lo scambio tra gli elementi. Quando troviamo l’elemento più piccolo, lo scambiamo con l’elemento alla posizione i utilizzando questa variabile temporanea.

Ecco dunque come utilizziamo la variabile temporanea:

t = a[min];
a[min] = a[i];
a[i] = t;

Dove la variabile t è dunque una 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;

   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];
      a[min] = a[i];
      a[i] = t;
    }

   for(i = 0; i < 10; i++) {
      printf("%d ", a[i]);      
   }   
}

Prestazioni del selection sort

L’algoritmo selection sort effettua N(N−1)/2 confronti, quindi la sua complessità è dell’ordine di θ(n2).

Sebbene questa complessità possa renderlo meno efficiente rispetto ad altri algoritmi come il mergesort o il quicksort, la sua semplicità lo rende una scelta ragionevole per piccoli insiemi di dati o quando la facilità di implementazione è una priorità.

Conclusioni

In questa lezione abbiamo implementato l’algoritmo di selection sort in linguaggio C, comprendendo i suoi principi fondamentali e la sua implementazione pratica. Nelle future lezioni, esamineremo ulteriori algoritmi di ordinamento e approfondiremo le loro applicazioni e prestazioni.

Alcuni link utili

Corso linguaggio C

Indice tutorial linguaggio C

Array o vettori

Quick sort in linguaggio C

Merge sort in linguaggio C

Insertion Sort in lingaggio C

Somma elementi diagonale principale di una matrice

Esercizio con le matrici in C

Triangolo di Tartaglia in C