Question

que es el metodo de insercion

Answer 1

Es un algoritmo de ordenamiento, con una complejidad asíntotica superior cuadrática, es decir O(n^2).

Básicamente el algoritmo lo que hace es intercambiar los elementos de tal forma que por cada intercambio, una parte del arreglo se irá ordenando, dicha parte crecerá, hasta que quede ordenado todo el arreglo.

La analogía del insertion sort, es la de una mano de poker, donde al recibir los elementos (desordenadamente), tu intercambias cartas, de tal forma que se ordene.

El método de insertion, ordena los elementos, del inicio hasta el final, esto quiere decir que la sublista ordenada, siempre será del inicio, no obstante, algunos casos requiere hacerse al revés, entonces el algoritmo recibe  otro nombre.


1 6 2 8 9 4 3  Arreglo original
1 6 2 8 9 4 3  Primera iteración
1 2 6 8 9 4 3  Segunda iteración
1 2 6 8 9 4 3  Tercera iteración
1 2 6 8 9 4 3  Cuarta iteración
1 2 4 6 8 9 3  Quinta iteración
1 2 3 4 6 8 9  Sexta iteración

https://en.wikipedia.org/wiki/Insertion_sort#Relation_to_other_sorting_algorithms