Selection Sort

di

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

  • da 2 a N
  • da 3 a N
  • …
  • da N-1 a N

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

ss1

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;