Implementazioni di algoritmi/Selection sort

Wikibooks, manuali e libri di testo liberi.

L'ordinamento per selezione (selection sort) è un algoritmo di ordinamento che opera in place ed in modo simile all'ordinamento per inserzione; seleziona il numero minore nella sequenza di partenza e lo sposta nella sequenza ordinata; di fatto la sequenza viene suddivisa in due parti: la sottosequenza ordinata, che occupa le prime posizioni dell'array, e la sottosequenza da ordinare, che costituisce la parte restante dell'array. L'algoritmo è di tipo non adattivo, ossia il suo tempo di esecuzione non dipende dall'input ma dalla dimensione dell'array.

I passi sono i seguenti:

• si inizializza un puntatore i che va da 1 a n (dove n è la lunghezza dell'array).
• Si cerca il più piccolo elemento dell'array
• Scambia l'elemento più piccolo con l'elemento alla posizione i
• Incrementa l'indice i e si torna al passo uno fino alla fine dell'array.

[modifica] Implementazioni

Seguono alcuni esempi di implementazione in vari linguaggi (ordinamento crescente).

[modifica] C++

void selection(int n,float v[])
{
  int i,minimo,j,posto;
  float temp;
  for(i=0;i<n-1;i++)
  {
     minimo=v[i];
     posto= i;
 
     for(j=i+1;j<n;j++)
     {
         if(v[j]<minimo)
         {
           minimo=v[j];
           posto=j;
         }
     }
 
    temp=v[posto];
    v[posto]=v[i];
    v[i]=temp;
  }
}

[modifica] C

void selection(double a[], unsigned long N) {
  int i, j, min; 
  double 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;
  }
}

[modifica] 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);
   }
}

[modifica] Pascal

const dim=20;
procedure SelectionSort(var a: array[1..dim] of integer);
var
    n,i,j,posmin,aus:integer;
begin
 for i:=1 to n-1 do 
  begin
    posmin:= i;
    for j:=(i+1) to n do
      if a[j]< a[posmin] then
        posmin:= j;
 
    aus:= a[i];
    a[i]:= a[posmin];
    a[posmin]:= aus;
  end;
end;

[modifica] PHP

function selection_sort(&$a) {
 
  for($i = 1; $i < count($a)-1; $i++) {
    $min_index = $j;
    for($j = $i + 1; $j < count($a); $j++)
      if ($a[$j] < $a[$i])
        $min_index = $j;
    $transfer = $a[$min_index];
    $array[$min_index] = $a[$i];
    $array[$i] = $transfer;
  }
}

[modifica] Python

def selection(array):
    for i in xrange(len(array)-1):
        m=i
 
        for j in xrange(i+1,len(array)):
            if array[j]<array[m]: m=j
 
 
        array[i], array[m] = array[m], array[i]

[modifica] Altri progetti

• Wikipedia contiene una voce riguardante questo algoritmo