Algoritmo de Ordenación por selección

Este algoritmo Consiste en encontrar el menor de todos los elementos del arreglo o vector e intercambiarlo con el que está en la primera posición.  Luego el segundo más pequeño, y así sucesivamente hasta ordenarlo todo. 

Como todo algoritmo, es una secuencia de pasos, a continuación se presentan las diferentes condiciones a seguir en Ordenación por selección:

•      Buscar el mínimo elemento de la lista

•      Intercambiarlo con el primero

•      Buscar el siguiente 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.

Para una representación un poco más visual se presenta este ejemplo de pseudocódigo:

para i=1 hasta n-1;

mínimo = i;

para j=i+1

hasta n

si lista[j] < lista[mínimo]

entonces mínimo = j ;

fin si

fin para intercambiar(lista[i], lista[mínimo ])

fin para.

Algunas de las ventajas de utilizar este Algoritmo son:

ü  Es fácil su implementación.

ü  No requiere memoria adicional.

ü   Realiza pocos intercambios.

ü  Tiene un rendimiento constante, pues existe poca diferencia entre el peor y el mejor caso.

Al igual que ventajas tiene desventajas:

ü  Es lento y poco eficiente cuando se usa en listas grandes o medianas.

ü   Realiza numerosas comparaciones.

 

Ejemplo de una codificación del Algoritmo por Ordenación de selección:

template <class T>void ordena_seleccion(vector<T>& v){

for(int i = 0; i < v.size() - 1; ++i)

{

int min = i;

for (int c = i + 1; c < v.size(); ++c) {

if (v[min] > v[c]) min = c;

}

T aux = v[i];

v[i] = v[min];

v[min] = aux;

}}

Referencias:

• http://www.ecured.cu/index.php/Algoritmo_de_ordenamiento_por_selecci%C3%B3n
• https://es.wikipedia.org/wiki/Ordenamiento_por_selecci%C3%B3n