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

package main
import (
"fmt"
)
// InsertionSort Ordena un []int utilizando ordemaniento por inserción
func InsertionSort(input []int) {
fmt.Print("\n===========================================\n")
fmt.Printf("ENTRADA: %v\n", input)
// Nuestro contador de pasos
stepCounter := 1
// Vamos a evaluar cada valor del slice
for i, v := range input {
// El primero lo omitimos pues no hay nada con qué compararlo.
if i < 1 {
continue
}
// Recorremos cada posición anterior hasta encontrar un valor menor al
// actual
for j := i - 1; j >= 0; j-- {
fmt.Printf(
"--------------- [ PASO %v ] ---------------\n",
stepCounter,
)
fmt.Printf("%v > %v = %v\n", input[j], v, input[j] > v)
stepCounter++
// Si el valor anterior es menor o igual al que estamos comparando
// hemos encontrado su posición final
if input[j] <= v {
fmt.Printf("%v\n", input)
break
}
// De lo contrario, intercambiamos los valores de ambas posiciones
input[i] = input[j]
input[j] = v
// actualizamos la posición del número que estamos evaluando
i--
// Estado actual del slice
fmt.Printf("%v\n", input)
}
}
fmt.Print("===========================================\n\n")
}
func main() {
// El slice que deseamos ordenar
var unsorted = []int{100, 6, 34, 28, 97, 23, 61, 2, 7, 1, 44, 0}
InsertionSort(unsorted)
// Imprimimos el resultado final
fmt.Printf("RESULTADO: %v", unsorted)
}
view raw main.go hosted with ❤ by GitHub

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

main.go.log