Ordenamiento por selección

De Wikipedia, la enciclopedia libre

El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O(n²) operaciones para ordenar una lista de n elementos.

Su funcionamiento es el siguiente:

• Buscar el mínimo elemento de la lísta
• Intercambiarlo con el primero
• Buscar el mínimo en el resto de la lista
• Intercambiarlo con el segundo

Y en general:

• Buscar el mínimo elemento entre una posición i y el final de la lista
• Intercambiar el mínimo con el elemento de la posición i

De esta manera se puede escribir el siguiente seudocódigo para ordenar una lista de n elementos indexados desde el 1:

iterar i desde 1 hasta n-1
    minimo = i;
    iterar j desde i+1 hasta n
        si lista[j] < lista[minimo] entonces minimo = j
    intercambiar(lista[i], lista[minimo])

[editar] Implementaciones

C:

int minimo=0;
for(i=0 ; i<n-1 ; i++)
{
   minimo=i;
   for(j=i+1 ; j<n ; j++)
   {
      if (x[minimo] > x[j]) minimo=j;
   }
   temp=x[minimo];
   x[minimo]=x[i];
   x[i]=temp;
}

Implementación en WinPseudo 1.3:

INICIO Programa16 - Selection Sort. Herbert Schildt, "Advanced C", Pag. 9.
  VAR
     VECTOR   Vect[25]
     NUMERICO a
     NUMERICO b
     NUMERICO c
     NUMERICO Aux
     NUMERICO Cant
  FIN-VAR

  Cant = 25

  a = 0
  MIENTRAS (a < Cant)
     Vect[a] = Cant - a
     a = a + 1
  FIN-MIENTRAS

  a = 0
  MIENTRAS (a < Cant - 1)
     c = a
     Aux = Vect[a]
     b = a + 1
     MIENTRAS (b < Cant)
        SI (Vect[b] < Aux)
           c = b
           Aux = Vect[b]
        FIN-SI
        b = b + 1
     FIN-MIENTRAS
     Vect[c] = Vect[a]
     Vect[a] = Aux
     a = a + 1
  FIN-MIENTRAS

  a = 0
  MIENTRAS (a < Cant)
     IMPRIMIR ENTERO (Vect[a])
     IMPRIMIR NL
     a = a + 1
  FIN-MIENTRAS

FINAL

Basic:

For i = 1 To n - 1
   minimo = i
   For j = i + 1 To n
      If x(minimo) > x(j) Then
         minimo = j
      End If
   Next j
   temp = x(i)
   x(i) = x(minimo)
   x(minimo) = temp
Next i