Implementazioni di algoritmi/Selection sort

L'ordinamento per selezione (selection sort) è un algoritmo di ordinamento che opera internamente;

L'algoritmo opera una divisione in due parti della struttura, sottosequenza ordinata e sottosequenza non ordinata. Partendo dal primo elemento, si ricerca quello più piccolo (o più grande) e lo si scambia inizialmente con l'elemento di partenza, ad ogni iterazione, l'elemento minimo della sottosequenza non ordinata viene spostato nella prima posizione della stessa. Dopo n-1 passi (dove "n" è la lunghezza della struttura da ordinare) di ricerca e scambio, gli elementi saranno ordinati

Risulta poco efficiente, per la sua complessità esponenziale, ma facile da implementare.

Il modo più semplice, per descrivere questo ordinamento interno, è quello di usare una struttura statica, quindi un array.

I passi sono i seguenti:

1. Viene Dichiarato e inizializzato un array contenente n elementi (quindi la lunghezza dell'array è n)
2. Si inizializza un indice i di un ciclo che va da 0 a n-1
3. Si crea un sotto ciclo che inizializza il suo indice j (ogni volta che viene chiamato) con i+1 e arriva fino a n
4. Si cerca il più piccolo elemento(o più grande) dell'array
5. Si scambia l'elemento più piccolo(o più grande) con l'elemento alla posizione i
6. Viene incrementato l'indice i e si torna al passo tre fino alla fine del primo ciclo.

Implementazioni

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

C++

void selection_sort(int arr[], int n)
{
    int i, j, indice_minimo, temp;

    for (i = 0; i < n-1; i++)
    {
        //Cerco l'elemento più piccolo dell'array disordinato
        indice_minimo= i;

        for (j = i+1; j < n; j++)
        {
        	if (arr[j] < arr[indice_minimo])
        	{
        	     indice_minimo= j;
        	}
        }

        //Scambio i valori
        temp= arr[indice_minimo];
        arr[indice_minimo]= arr[i];
        arr[i]= temp;

    }
}

C

#define ITEM long // tipo array da ordinare
void  selectionSort(ITEM *Array,int Array_Length){  
    ITEM minimo=0;
    int i=0, indiceMinimo=0, j=0;
    for(i=0; i<Array_Length-1; i++){
        minimo = Array[i];
        indiceMinimo = i;
        for(j=i+1; j<Array_Length; j++){
            if(Array[j] < minimo){
                minimo = Array[j];
                indiceMinimo = j;
            }
        }        
        Array[indiceMinimo]=Array[i];
        Array[i]=minimo;        
    }
}

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;
       }
      if(posMin!=i)
        scambio(a,i,posMin);
      System.out.println("KEKW");
   }
}

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

Altri progetti

• Wikipedia

• Wikipedia contiene una voce su questo algoritmo