Implementazioni di algoritmi/Selection sort

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.

Implementazioni

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

C++

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

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;
  }
}

Fortran

       SUBROUTINE selection_sort(N,A)
       !
       ! Questa subroutine (va richiamata da un programma) ordina 
       ! un insieme numerico dato in senso non decrescente applicando
       ! l'algoritmo di ordinamento per selezione (SELECTION SORT)
       !
 
       ! Dichiarazione delle variabili
       IMPLICIT NONE ! impossibilità di utilizzare all'interno della subroutine variabili non dichiarate (nessuna implicita)
       INTEGER, INTENT(IN) :: N ! è l'estensione dell'insieme (l'array) da ordinare
       REAL, DIMENSION(N), INTENT(INOUT) :: A ! l'insieme che entra disordinato nella subroutine e ne esce ordinato
       ! Dichiarazione variabili locali
       INTEGER :: I, J ! indici di ciclo
       REAL :: TEMP, MINI ! TEMP è una variabile d'appoggio, mentre MINI è la posizione nell'array del primo elemento non ordinato
 
       ! Corpo del programma
       ext_cyc: DO I=1,N-1
        MINI=I
        int_cyc: DO J=I+1,N
         IF ( A(J) < A(MINI) ) THEN
          MINI=J
         END IF
         TEMP=A(I)
         A(I)=A(MINI)
         A(MINI)=TEMP
        END DO int_cyc
       END DO ext_cyc
 
       RETURN
       END SUBROUTINE selection_sort

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

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;

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;
  }
}

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]
        return array

VBasic

        For i = 1 To n - 1
            min = i
            For j = i + 1 To n
                If n1(min) > n1(j) Then
                    min = j
                End If
            Next
            aus = n1(i)
            n1(i) = n1(min)
            n1(min) = aus
        Next

Altri progetti

• Wikipedia

• Wikipedia contiene una voce riguardante questo algoritmo