Selection Sort

Algoritmo intuitivo e più veloce del bubble sort.

Si può individuare il valore minimo in un array V e scambiarlo con il valore alla prima posizione.

PosMin:=1;
For j:=2 To N
   If(V[j] < V[posMin]) Then
      PosMin=j;
SCAMBIA(V, 1, PosMin)

In questo modo l'elemento alla posizione 1 occupa definitivamente il posto che gli spetta...

Ripetendo la stessa operazione con i sottovettori

andranno al loro posto gli elementi alla posizione 2, 3, ..., N-1.
L'elemento alla posizione N occuperà l'unico posto rimasto libero per l'elemento più grande...

Procedure SELESORT(Var V: Vettore; N: Integer);
Var
    PosMin, i, j: Integer;
Begin
    For i:=1 To N-1 Do
        Begin
            PosMin:=i;
            For j:=i+1 To N Do
                If(V[j] < V[PosMin]) Then
                    PosMin:=j;
            SCAMBIA(V[i], V[PosMin]);
        End;
End;

Osserva

Miglioramento

Con un If(...) Then... aggiuntivo si può evitare di eseguire inutilmente la SCAMBIA() quando un elemento occupa già il posto giusto

Procedure SELESORT(var V: Vettore; N: Integer);
Var
   PosMin, i, j: Integer;
Begin
   For i:=1 To N-1 Do
      Begin
         PosMin:=i;
         For j:=i+1 To N Do
            If(V[j] < V[PosMin]) Then
               PosMin:=j;
         If(PosMin <> i) Then
            SCAMBIA(V[i], V[PosMin]);
      End;
End;