El algoritmo de Selección para ordenar en uno de los más sencillos; así como también es uno de los más lentos. Su funcionamiento se basa en seleccionar siempre el elemento más pequeño para acomodarlo dentro de la secuencia.
Para realizar el análisis utilicemos el siguiente arreglo de números enteros.
La parte gris del arreglo de la izquierda son los elementos a intercambiar mientras que los elementos en gris del arreglo de la derecha ya están ordenados.
Análisis
Primero se encuentra el elemento más pequeño del arreglo (el más pequeño es 1) y lo coloca en la posición 0 intercambiándolo por el número que estaba en esa posición.
Ahora el algoritmo encuentra nuevamente el elemento más pequeño del arreglo a partir de la posición 1 (el más pequeño es 2) y lo intercambia con el elemento que se encuentra en la posición 1.
Nuevamente el algoritmo encuentra el elemento más pequeño del arreglo pero a partir de la posición 2 (ahora el más pequeño es 3) y lo intercambia con el elemento que se encuentra en la posición 2.
En este caso existen dos elementos con el mismo valor; el algoritmo toma el primer de ellos.
Una vez más buscamos el elemento más pequeño, pero ahora desde la posición 3 (el elemento más pequeño sigue siendo 3 debido a que se repite) y lo intercambiamos por el elemento que se encuentra en la posición 3.
Ahora, a partir de la posición 4 buscamos el elemento más pequeño que es 5, pero se encuentra colocado en esa misma posición, por lo que esta ordenado y no hay intercambio.
Ahora el algoritmo debe encontrar el elemento más pequeño a partir de la posición 5 (el elemento más pequeño es 6) e intercambiarlo con el elemento en la posición 5.
Ahora nuestro arreglo ha quedado ordenado. El último elemento debe ser el mayor y no es necesario comprobarlo debido a que la parte del algoritmo que encuentra el elemento más pequeño y de intercambiarlos de repite n – 1; donde n es el numero de elementos.
Código en C++
Una vez que hayamos entendido como funciona el método de selección para ordenar elementos podemos diseñar nuestro código fuente.
void seleccion(int array[], int size)
{
for (int fill = 0; fill != size -1; ++fill){
int pos_min = fill;
for(int next = fill + 1; next != size; ++next){
if (array[next] < array[pos_min]) {
pos_min = next;
}
}
if (fill != pos_min) {
std::swap(array[pos_min], array[fill]);
}
}
}Test
Pongamos a prueba nuestra función en C++.
#include <iostream>
using namespace std;
void seleccion(int array[], int size)
{
for (int fill = 0; fill != size -1; ++fill){
int pos_min = fill;
for(int next = fill + 1; next != size; ++next){
if (array[next] < array[pos_min]) {
pos_min = next;
}
}
if (fill != pos_min) {
std::swap(array[pos_min], array[fill]);
}
}
}
int main (int argc, char *argv[])
{
int numeros[] = {9,3,5,3,2,1,6,7};
/* Imprimimos el arreglo original */
for (int i = 0; i < 7; ++i){
cout << numeros[i] << " ";
}
cout << endl;
seleccion(numeros, 7);
/* Imprimimos el arreglo ordenado */
for (int i = 0; i < 7; ++i){
cout << numeros[i] << " ";
}
}$ g++ -o Seleccion Seleccion.cpp $ ./Seleccion 9 3 5 3 2 1 6 1 2 3 3 5 6 9