Algoritmo de ordenamiento por selección (Selection Sort)

Artículo perteneciente a la sección de algoritmos

Este artículo es una evolución del algoritmo de ordenación por burbuja

Hola a todos,

Hace poco os explique el algoritmo de ordenación por burbuja y el de ordenación por burbuja bidireccional. Pese a que este segundo es una evolución un poco mejor que el original, el problema de que usa demasiada memoria sigue ocurriendo.

En las arquitecturas hardware (tantos las actuales, como las antiguas, y seguramente también las futuras) lo que más limita la velocidad de ejecución de un programa es el acceso a memoria. Si nuestro algoritmo usa de forma intensiva la memoria lo más normal es que su rendimiento sea bajo.

Con esta premisa nació el algoritmo de ordenación por selección.  La idea es simple. Busco el elemento más pequeño de la lista, y lo intercambio con el elemento de la primera posición... busco el segundo elemento más pequeño y lo intercambio con el elemento de la segunda posición. Con esto se hace más o menos el mismo número de comparaciones que se hacen con el algoritmo de burbuja tradicional, pero con muchos menos movimientos  de memoria, y por lo tanto con un rendimiento claramente superior.

Un ejemplo de código de este algoritmo sería el siguiente:

void LPVector::SelectionSort(void)
{
int i,j,indmin=0;
float min = v[0];

for ( i = 0 ; i < (n-1) ; ++i)
{
indmin = i;
min = v[i];
for( j = i+1 ; j < n ; ++j)
{
if(v[j] < min )
{
indmin = j;
min = v[j];
}
}

v[indmin] = v[i];
v[i] = min;
}
}


No podemos decir que sea un algoritmo eficiente (su coste depende de forma cuadrática con la longitud del vector), pero si que podemos asegurar que solo hará tantos movimientos de memoria como elementos haya en el vector, y esto ya es una clara mejora.

En breve haré una lista comparativa con los costes de cada algoritmo en diferentes situaciones para que os hagáis una idea.

Espero que os sirva de referencia

Nos vemos