La idea del Selection Sort es ordenar un arreglo, manteniendo el arreglo ordenado del lado izquierdo, y el desordenado del lado derecho (o como más te guste).
A medida que el algoritmo avanza, el tamaño de la parte ordenada va creciendo, y el de la parte desordenada decreciendo.
Un seudocódigo podría ser el siguiente:
SelectionSort( array desordenado, largo de array ) -> array ordenado
desde i=0 a (largo-2)
pos_men = menor(array, i) // posicion del elemento con menor valor desde i
intercambiar(pos_men,i)
fin-desde
Como verás se busca el elemento más chico (se guarda su posición en pos_men) y se inserta en el primer lugar, luego entre los que quedan por ordenar se busca el más chico y se inserta en el segundo lugar, así hasta el anteúltimo elemento. El último elemento quedará automáticamente ordenado en su lugar.
Si N es el largo del array, para insertar el primer elemento se hacen N-1 comparaciones, para el segundo N-2 y así sucesivamente hasta 1.
Por lo que en total se hacen (N-1 + N-2 + N-3 +...+ 2 + 1) comparaciones, o lo que es lo mismo la sumatoria de los primero N-1 naturales, cuyo valor es:
N(N-1)/2
Espero se haya entendido.
Saludos.
Autor
En línea
