Implementazioni di algoritmi/Selection sort

Wikibooks, manuali e libri di testo liberi.
CopertinaImplementazioni di algoritmi/Copertina


L'ordinamento per selezione (selection sort) è un algoritmo di ordinamento che opera internamente; partendo dal primo elemento , si ricerca quello più piccolo (o più grande) e lo si scambia con l'elemento di partenza. Dopo n-1 passi (dove "n" è la lunghezza della struttura da ordinare) di ricerca e scambio , gli elemento 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[modifica]

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

C++[modifica]

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[modifica]

#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[modifica]

       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[modifica]

 
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[modifica]

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[modifica]

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[modifica]

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[modifica]

        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[modifica]