Selection sort

Il selection sort, ordinamento per selezione, è uno degli algoritmi di ordinamento più intuitivi (e di facile realizzazione). L'ordinamento avviene selezionando ad ogni iterazione il valore più piccolo e scambiando quest'ultimo con il valore in testa alla lista da ordinare e non ancora ordinato (prima iterazione). Le successive iterazioni effettueranno, allora, la ricerca del valore più piccolo su un insieme di valori sempre più ridotti. Un indice indica la posizione della lista che si sta ordinando. Ad ogni iterazione, dunque, la lista ordinata aumenta di un valore fino a prevedere tutti i valori della lista di partenza. Queste le fasi previste dall'algoritmo:

• inizializzare un puntatore i che va da 0 ad n-1, con n lunghezza dell'array (il primo elemento dell'array ha indice 0);
• cercare il valore più piccolo nell'array;
• scambiare l'elemento più piccolo, appena trovato, con l'elemento puntato da i;
• incrementare i e ripetere la ricerca del valore più piccolo fino a scorrere tutti gli elementi dell'array;

Di seguito propongo una realizzazione dell'algoritmo in linguaggio C:

/* selectionsort */
#include <stdio.h>

#define LENGTH 10

void selectionSort(int *array,int length);
int search_min(int *array,int begin,int end);
void swap(int *x, int *y);

int main(void) {
   int i,array[LENGTH]={1,8,4,0,2,5,6,3,7,9};
   selectionSort(array, LENGTH);
   printf("array: ");
   for (i=0;i<LENGTH;i++)
      printf("%d, ",array[i]);
   printf("\b\b;\n");
   return 0;
}

void selectionSort(int *array,int length) {
   int i,i_min;
   for (i=0;i<length;i++) {
      if ((i_min=search_min(array,i,length))==-1)
         printf("Errore nella chiamata alla funzione!");
      else swap(&array[i],&array[i_min]);
   }
}

int search_min(int *array,int begin,int end) {
   int i,temp_i;
   if (begin<end) {
      temp_i=begin;
      for (i=begin+1;i<end;i++) {
         if (array[i]<array[temp_i]) temp_i=i;
      }
      return temp_i;
   }
   else return -1;
}

void swap(int *x, int *y) {
   int temp=*x;
   *x=*y;
   *y=temp;
}