Ordenamiento por inserción | Insert Sort

Repo: https://github.com/umarquez/100DaysOfC0D3/tree/master/1-insertion_sort

El ordenamiento por inserción (insertion sort en inglés) es una manera muy natural de ordenar para un ser humano, y puede usarse fácilmente para ordenar un mazo de cartas numeradas en forma arbitraria. Requiere O(n²)operaciones para ordenar una lista de n elementos. https://es.wikipedia.org/wiki/Ordenamiento_por_inserci%C3%B3n

¿Cómo funciona?

Este algoritmo consiste en comparar cada elemento de la lista con el elemento anterior, intercambiándolos si el elemento actual fuera menor y hasta no encontrar más elementos con valores mayores hacia el inicio de la lista.

Ejemplo:

Supongamos que debemos ordenar la siguiente lista:

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

Paso 1:

  • Tomamos el segundo elemento de la lista lista[1] y lo comparamos con el anterior lista[0], si el actual es menos, lo intercambiamos.

Paso 2

  • Tomamos el siguiente elemento lista[2] y lo comparamos con el segundo lista[1], si es menor lo intercambiamos.

lista[2] < lista[1]

Paso 3

  • Si intercambiamos, comparamos el elemento actual (ahora lista[1])con al anterior lista[0] e intercambiamos si este sigue siendo menor al comparado.

lista[1] < lista[0]

Paso 4–6

  • Tomamos el siguiente elemento de la lista lista[3] y lo intercambiamos con el índice inferior lista[2] si este fuera mayor. Continuamos hasta no encontrar elementos mayores.

lista[3] < lista[0], lista[1], lista[2]

Paso 7 — 10

  • Repetimos los mismos pasos con el elemento restante lista[4]

lista[4] < lista[0], lista[1], lista[2], lista[3]

Resultado final

[]lista{1,2,3,4,5}

Implementación en Go

https://play.golang.org/p/B-GTDav5eTP

main.go.log