Ordenamiento por selección | Selection Sort

Repo: https://github.com/umarquez/100DaysOfC0D3/tree/master/3-selection_sort

¿Cómo funciona?

Se trata de un algoritmo de ordenamiento del tipo O(n²)solo que en este caso no desplazaremos cada elemento una posición a la vez, como en el Ordenamiento por inserción, en su lugar nos enfocaremos en buscar el número menor del resto de la lista y una vez lo encontremos, lo intercambiaremos por el valor de la posición que estamos procesando.

Ejemplo:

Trataremos de ordenar la siguiente lista de enteros:

\[\]int{5,2,4,1,3}
\[\]int{5,2,4,1,3}

Pasos 1 →4

  • Tomamos el primer elemento de la lista y recorremos el resto de elementos hasta encontrar el número con el menor valor.
  • Intercambiamos este con el primer elemento de la lista, pues se tratará del elemento más pequeño de toda la lista.

\[\]int{5,2,4,1,3} →\[\]int{1,2,4,5,3}
\[\]int{5,2,4,1,3} →\[\]int{1,2,4,5,3}

Pasos 5 →7

  • Enseguida tomamos el segundo elemento de la lista y recorremos el resto de los elementos en busca de un elemento menor a este

\[\]int{1,2,4,5,3}
\[\]int{1,2,4,5,3}

En este cano, no será necesario realizar ningún intercambio pues el elemento ya se encuentra en su ubicación final.

Pasos 8→9

  • Tomamos el tercer elemento de la lista y buscamos el siguiente elemento más pequeño para intercambiarlo con este.

\[\]int{1,2,4,5,3} → \[\]int{1,2,3,5,4}
\[\]int{1,2,4,5,3} → \[\]int{1,2,3,5,4}

Paso 10

  • finalmente evaluamos si el último elemento debe ser intercambiado.

\[\]int{1,2,3,5,4} → \[\]int{1,2,3,4,5}
\[\]int{1,2,3,5,4} → \[\]int{1,2,3,4,5}

Resultado final

\[\]int{1,2,3,4,5}
\[\]int{1,2,3,4,5}

Implementación en Go

https://play.golang.org/p/S3topeqWdxS

main.go.log
main.go.log