Implementazioni di algoritmi/Selection sort

L'ordinamento per selezione (selection sort) è un algoritmo di ordinamento che opera in modo simile all'ordinamento per inserzione; seleziona il numero minore nella sequenza di partenza e lo sposta nella sequenza ordinata.

I passi sono i seguenti:

• Si cerca il più piccolo elemento dell'array
• Scambia l'elemento più piccolo con l'elemento in prima posizione
• Incrementa l'indice e ricomincia il ciclo

Implementazioni

Seguono alcuni esempi di implementazione in vari linguaggi.

C

void selection(void) {
  int i, j, min, t; 

  for (i=0; i < N-1; i++) {
    min = i;

    for (j= i + 1; j <= N; j++)
      if (a[j] < a[min]) min = j;

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

Java

 
 private static void scambio(Object a[], int ind1, int ind2 ){
     Object tmp = a[ind1];    
       a[ind1] = a[ind2];
       a[ind2] = tmp;   
   }
 public static void selectionSort(Object a[]) {    
        for (int i=0; i<a.length-1; i++) {
        int posMin = i;
            for (int j=i+1; j<a.length; j++) 
                if (((Comparable)a[j]).compareTo(a[posMin])<0) posMin = j;
            scambio(a,i,posMin);
    }
 }
 

Pascal

program SelectionSort(input,output);
const dim=20;
var a: array[1..dim] of integer;
    n,i,j,pos,min,aus:integer;
begin
 // Creazione vettore di n elementi (con 1<=n<=dim)
 pos:=0; 
 for i:=1 to n-1 do begin
    min:= a[i];
    for j:=(i+1) to n do begin
      if a[j]< min then begin
        min:= a[j];
        pos:= j;
      end;
    end;
    aus:= a[i];
    a[i]:= min;
    a[pos]:= aus;
  end;
 // Stampa del vettore
 readln;
end.
 

Analisi delle prestazioni

Il ciclo interno è un semplice test per confrontare l'elemento corrente con il minimo elemento trovato fino a quel momento (più il codice per incrementare l'indice dell'elemento corrente e per verificare che esso non ecceda i limiti dell'array). Lo spostamento degli elementi è fuori dal ciclo interno: ogni scambio pone un elemento nella sua posizione finale quindi il numero di scambi è pari a $N-1$ (dato che l'ultimo elemento non deve essere scambiato). Il tempo di calcolo è determinato dal numero di confronti.

L'ordinamento per selezione effettua circa $N^{2}/2$ confronti ed $N$ scambi.

La complessità di tale algoritmo è dell'ordine di ${\frac {n(n-1)}{2}}={\frac {n^{2}-n}{2}}=O(n^{2})$

Casi limite

Un inconveniente dell'algoritmo di ordinamento per selezione è che il tempo di esecuzione dipende solo in modo modesto dal grado di ordinamento in cui si trova il file. La ricerca del minimo elemento durante una scansione del file non sembra dare informazioni circa la posizione del prossimo minimo nella scansione successiva. Chi utilizza questo algoritmo potrebbe stupirsi nel verificare che esso impiega più o meno lo stesso tempo sia su file già ordinati che su file con tutte le chiavi uguali, o anche su file ordinati in modo casuale.

Nonostante l'approccio brutale adottato, ordinamento per selezione ha un'importante applicazione: poichè ciascun elemento viene spostato al più una volta, questo tipo di ordinamento è il metodo da preferire quando si devono ordinare file costituiti da record estremamente grandi e da chiavi molto piccole. Per queste applicazioni il costo dello spostamento dei dati è prevalente sul costo dei confronti e nessun algoritmo è in grado di ordinare un file con spostamenti di dati sostanzialmente inferiori a quelli dell'ordinamento per selezione.