Ordenamiento por inserción: concepto y ejemplo detallado
Contenido del curso
El ordenamiento por inserción es uno de los algoritmos más comunes que estudian los Científicos del Cómputo. Es intuitivo y fácil de implementar, pero es muy ineficiente para listas de gran tamaño.
Una de las características del ordenamiento por inserción es que ordena en "su lugar." Es decir, no requiere memoria adicional para realizar el ordenamiento ya que simplemente modifican los valores en memoria.
La definición es simple:
Una lista es dividida entre una sublista ordenada y otra sublista desordenada. Al principio, la sublista ordenada contiene un solo elemento, por lo que por definición se encuentra ordenada.
A continuación se evalua el primer elemento dentro la sublista desordenada para que podamos insertarlo en el lugar correcto dentro de la lista ordenada.
La inserción se realiza al mover todos los elementos mayores al elemento que se está evaluando un lugar a la derecha.
Continua el proceso hasta que la sublista desordenada quede vacia y, por lo tanto, la lista se encontrará ordenada.
Veamos un ejemplo:
Imagina que tienes la siguiente lista de números:
7, 3, 2, 9, 8
Primero añadimos 7 a la sublista ordenada:
7, 3, 2, 9, 8
Ahora vemos el primer elemento de la sublista desordenada y lo guardamos en
una variable para mantener el valor. A esa variable la llamaremos valor_actual.
Verificamos que 3 es menor que 7, por lo que movemos 7 un lugar a la derecha.
7, 7, 2, 9, 8 (valor_actual=3)
3 es menor que 7, por lo que insertamos el valor en la primera posición.
3, 7, 2, 9, 8
Ahora vemos el número 2. 2 es menor que 7 por lo que lo movemos un espacio a la derecha y hacemos lo mismo con 3.
3, 3, 7, 9, 8 (valor_actual=2)
Ahora insertamos 2 en la primera posición.
2, 3, 7, 9, 8
9 es más grande que el valor más grande de nuestra sublista ordenada por lo que lo insertamos directamente en su posición.
2, 3, 7, 9, 8
El último valor es 8. 9 es más grande que 8 por lo que lo movemos a la derecha:
2, 3, 7, 9, 9 (valor_actual=8)
8 es más grande que 7, por lo que procedemos a insertar nuestro valor_actual.
2, 3, 7, 8, 9
Ahora la lista se encuentra ordenada y no quedan más elementos en la sublista desordenada.
Antes de ver la implementación en Python, trata de implementarlo por ti mismo y compártenos tu algoritmo en la sección de comentarios.
Esta es una forma de implementar el algoritmo anterior:
def ordenamiento_por_insercion(lista): for indice in range(1, len(lista)): valor_actual = lista[indice] posicion_actual = indice while posicion_actual > 0 and lista[posicion_actual - 1] > valor_actual: lista[posicion_actual] = lista[posicion_actual - 1] posicion_actual -= 1 lista[posicion_actual] = valor_actual
Luis Zabala
Cristian Benites Condori
Miguel Alexander Vásquez Ortega
Marlon Ramirez
Reinaldo Mendoza
Fernando Ciano
Angel Estrada
Mauricio Gonzalez Falcon
Osvaldo Olguín
Luis Fernando Cruz Carrillo
Jonathan Edwin Gutiérrez Olvera
Guillermo Garcia Beverido
Alejandro Barrios
Renato Agustín Lagos Albornoz
Víctor Isaac Arias García
Facundo Nicolás García Martoni
Profesor
Alberto Castro Flores
Juan Sebastian Mesa
Luis Francisco Ramírez López
Laura Camila Pinzón Casallas
Felipe Cortés
Arredondo Escoto Jose Antonio
Cristian Risueño Celedonio
Juan Sebastián Vargas Castañeda
Keler Antonio Araujo Olaya
Cristian Alejandro Velasco Cernas
Jose Antonio Rojas Ollarves
Manuel Espitia
Jose Antonio Rojas Ollarves
Noldia Chavez Cavero
Jherom Chacon
Jesús David Jaramillo Rincón
Jorge Leonardo Céspedes Tapia
José Martínez Santana
David Aroesti
Profesor
Clayton Jhordan Iliquin Zavaleta
Daniela Funes
Angel Estrada
Enzo Rafael Cárdenas Nicho
Yehosua Danilo Benitez Diaz
Rubén Cuello
Gabriel Andrés Alzate Acuña
No entiendo la razón de que esta explicación sea en texto y no en video, si es una de las mejores y preferidas por el tutor debería estar en un video y no la anterior :S
Este no era su favorito jsjs, es el siguiente el de ordenamiento por mezcla que lo invento Von Newman, este algoritmo realmente es parecida al de burbuja y su eficiencia tampoco es muy distinta.
Asi es, este no es su algoritmo preferido
Comparto una imagen, para una aquellos compañeros que le gusta ver la cosas de manera grafica.
Gracias por el ejemplo grafico
Perfecto, mucho mas claro que el detalle de la clase
Para el peor escenario, es decir, que la lista a ordenar esté ordenada en forma descendiente, ambos algoritmos tienen el mismo comportamiento, en la gráfica muestro cuantos pasos necesita cada algoritmo, para poder hacer la ordenación dependiendo del número de elementos a ordenar:
Sin embargo, tomando listas en orden aleatorio, claramente se ve la superioridad, del algoritmo de inserción:
Les comparto mi código:
import random import matplotlib.pyplot as plt def ordenamiento_insercion(lista): iteraciones = 0 for i in range(1,len(lista)): j = i while lista[j] < lista[j-1] and j > 0: #O(n) * O(n) = O(n*n) = O(n**2) lista[j],lista[j-1] = lista[j-1],lista[j] j -= 1 # print(lista) iteraciones +=1 return lista,iteraciones def ordenamiento_burbuja(lista): tam_list = len(lista) iteraciones = 0 for i in range(tam_list): # print(f'iteraciones {iteraciones}') for j in range(0,tam_list-i-1): #O(n) * O(n) = O(n*n) = O(n**2) if lista[j] > lista[j+1]: lista[j],lista[j+1] = lista[j+1],lista[j] iteraciones += 1 # print(lista) return lista,iteraciones def main(): # tamanio_lista = int(input('De que tamaño ser la lista: ')) # lista = [random.randint(0,tamanio_lista) for i in range(tamanio_lista)] iteraciones_ins_sor=[] iteraciones_bub_sor=[] tam_de_lista = [i for i in range(2,1000,10)] for tamanio_lista in range(2,1000,10): # lista = sorted([i for i in range(tamanio_lista)],reverse=True) lista = [random.randint(0,tamanio_lista) for i in range(tamanio_lista)] # print(lista) lista_ord_ins = ordenamiento_insercion(lista) lista_ord_bur = ordenamiento_burbuja(lista) iteraciones_ins_sor.append(lista_ord_ins[1]) iteraciones_bub_sor.append(lista_ord_bur[1]) # print(f'Iteraciones {lista_ord_ins[1]}\nLista Ordenada Insersion:\n') # print(lista_ord_ins[0]) # print(f'\nIteraciones {lista_ord_bur[1]}\nLista Ordenada Burbuja:\n') # print(lista_ord_bur[0]) # print(iteraciones_ins_sor) # print(iteraciones_bub_sor) iteraciones_ins_sor = (tam_de_lista,iteraciones_ins_sor) iteraciones_bub_sor = (tam_de_lista,iteraciones_bub_sor) data = (iteraciones_ins_sor, iteraciones_bub_sor) colors = ("red", "green") groups = ("Ordenamiento por Insercion", "Ordenamiento de burbuja") size = (30,10) # Create plot fig = plt.figure() ax = fig.add_subplot() for data, color, group, size in zip(data, colors, groups,size): x, y = data ax.scatter(x, y, alpha=0.8, c=color, edgecolors='none', s=size, label=group) plt.title('Iteraciones que necesita cada algoritmo, en el peor escenario') plt.xlabel('Tamanio de lista') plt.ylabel('Iteraciones') plt.legend(loc=2) plt.show() if __name__ == '__main__': main()
Gracias!
O(n**2)
Hola si les está costando entender este algoritmo aquí les dejo dos video que ayudan bastante a entenderlo. Saludos.
Explicación del algorítmo: https://www.youtube.com/watch?v=bB8Px8D9QdQ
Implementación del algorítmo: https://www.youtube.com/watch?v=PUudQLFI8bA
Gracias
uhhh chica, gracias por el dato...basicamente insercion echa los datos mas chicos pa'la izquierda, y bubble sort echa el mas grande, pa'la derecha. Thanks!
Explicado paso por paso ;)
def ordenamiento_insercion(lista): # crea un contador segun el largo de la lista para usar el indice como cursor for indice in range(1, len(lista)): # guarda el valor actual del cursor en una variable valor_actual = lista[indice] # ej: (5) # si el cursor es mayor que cero # y el numero anterior al cursor es mayor que el valor actual while indice > 0 and lista[indice - 1] > valor_actual: # ej: 7 > (5)? # el valor actual pasa a ser igual al numero anterior al cursor lista[indice] = lista[indice -1] # ej: [...7,(5)...] => [...7,(7)...] # se resta 1 al indice para posarnos en el numero anterior al cursor indice -= 1 # ej: [...(7),7...] # como insertamos el valor del numero anterior al cursor en la posicion actual, # ahora insertamos en la posicion del numero anterior, el valor que teniamos guardado lista[indice] = valor_actual # ej: [...(7),7...] => [...(5),7...] # y seguimos con el siguiente indice. return lista if __name__=='__main__': lista = [7,5,3,8,1,9,8,2] lista_ordenada = ordenamiento_insercion(lista) print(lista_ordenada)```
tremendo gracias
Muchas gracias
Comparto mi implementación:
def insertion_sort(some_list): for i in range(len(some_list)): for j in range(i, 0, -1): if some_list[j] < some_list[j - 1]: some_list[j], some_list[j - 1] = some_list[j - 1], some_list[j] continue break
hola facundo,
en la linea for j in range(i, 0, -1): como se comporta el ciclo?, como avanza se el limite es 0 pero el paso es negativo?
solo tengo una inquietud, qué este código no sería bubble sort?
<code> #Aqui les comparto un ejemplo que realice de ordenamiento por inserccion, cabe de mencionar que nos debes el video de este medoto @DavidAroesti import random def ordenamiento_por_insercion(lista): indice = len(lista) count = 0 for indice in range(1, len(lista)): count += 1 valor_actual = lista[indice] posicion_actual = indice while posicion_actual > 0 and lista[posicion_actual - 1] > valor_actual: lista[posicion_actual] = lista[posicion_actual - 1] posicion_actual -= 1 lista[posicion_actual] = valor_actual print(f'Se realizaron {count} movimientos!' ) return lista if __name__ == '__main__': tamano_de_lista = int(input('De que tamaño sera la lista?')) lista = [random.randint(0, 100) for i in range(tamano_de_lista)] lista_ordenada = ordenamiento_por_insercion(lista) print(lista_ordenada)
Esta muy bien, pero el counter debe aumentar dentro y luego del while ya que esto tambien significa que estas iterando, el while es practicamente un for mas dinamico guiado por estados y no por contadores.
El codigo seria algo asi:
# _*_ coding: utf-8 _*_ """Algorithm for sort lists""" import random, time def insertion_sort(lista): i = 0 for indice in range(1, len(lista)): valor_actual = lista[indice] posicion_actual = indice while posicion_actual > 0 and lista[posicion_actual - 1] > valor_actual: i += 1 lista[posicion_actual] = lista[posicion_actual - 1] posicion_actual -= 1 i += 1 lista[posicion_actual] = valor_actual return(lista, i) if __name__ == "__main__": len_of_list = int(input("How big should the list be? ")) lista = [random.randint(0,10000) for i in range(len_of_list)] print(*lista, sep=" ") tic = time.time() sort_list, i = insertion_sort(lista) toc = time.time() print(*sort_list, sep=" ") print(f'The list is sort in {round(toc-tic,4)}secs in {i} iterations') print(*sort_list, sep=",")
Excelente, gracias
Os dejo el código comentado por si os sirve.
# Módulo necesario para generar números aleatorios import random def ordenamiento_por_insercion(lista): # Recorre la lista for indice in range(1, len(lista)): # Guarda el valor actual y la posición actual valor_actual = lista[indice] posicion_actual = indice # Si no está en la primera posición y el elemento anterior es mayor que el actual while posicion_actual > 0 and lista[posicion_actual - 1] > valor_actual: # Le da al valor actual el valor y vuelve a la posición anterior lista[posicion_actual] = lista[posicion_actual - 1] posicion_actual -= 1 # Le da al valor actual (Que realmente es el anterior si ha entrado en el while) # el valor del principio. Realmente hace un intercambio de valores actual por anterior lista[posicion_actual] = valor_actual # Crea una lista con números aleatorios y la muestra. Luego la ordena y la muestra if __name__ == '__main__': tamano_de_lista = int(input('De que tamano sera la lista? ')) lista = [random.randint(0, 100) for i in range(tamano_de_lista)] print(lista) lista_ordenada = ordenamiento_por_insercion(lista) print(lista_ordenada)```
Muchas gracias! :3
Cristian, no es necesario para finalizar la funcion ordenamiento_por_insersion() realizar el return lista ??
Les comparto este video donde lo explican muy bien si quieren entender mejor el ordenamiento por inserción.
https://www.youtube.com/watch?v=bB8Px8D9QdQ&ab_channel=KhanAcademyEspa%C3%B1ol
Insertion sort: Este algoritmo es como arreglar las cartas que tienes en tu mano, por ejemplo:
Vez la primera carta que tienes que es "X", y esa la vas a cambiar por la posicion de la siguiente carta que es "Y" por que es menor que ella, luego cuando vas a a las siguiente la vas a separar y luego comparar con las que ya tienes del lado izquierdo su valor para colocarla en el lugar adecuado y asi sucesivamente aplicarla hasta que hayas terminado de arreglar las cartas en tu mano. Esto mismo se aplica en programacion con el posicionamiento de memoria de las variables.
esto es así? confirmen por favor. que lo entiendo perfecto pero no sé si es así.
Si amigo manuel asi mismo, es en el aporte yo hice un comentario con mis propias palabras pero puedes revisar mas contenido por fuera te recomiendo este video tambien:
Conceptos basicos
Insertion sort aplicado en Python
por si es que no quedo claro: https://www.youtube.com/watch?v=bB8Px8D9QdQ
Bueno a mi me gusta programar en inglés para que el código no parezca spanglish, no me juzguen ja, ja!
**Saqué una solución con solo 3 líneas de código en 1 solo bucle. **Me gasté 5 horas entendiendo perfectamente el problema y haciendo una prueba de escritorio en papel. Si corren el código verán la prueba de escritorio en pantalla con lujo de detalles; cuidado, al inicio ingresen valores de lista pequeños porque tiene que imprimir en pantalla miles de números y puede demorarse si elige un número muy grande.
Aprendí hoy que entender exactamente lo que quiere el cliente detalle por detalle y no solo el punto de partida y de legada; veo que es útil para construir programa que emule exactamente su forma de trabajar como si fuera su propia alma trabajando para no errar, calcando su manera de producir cada pequeño resultado.
Nota: podría considerarse O (n*n) porque i se incrementa y decrementa en múltiples ocasiones antes de salir del bucle.
Ejemplo autogenerado: Digite tamaño de lista: 4 Su lista es <<<< [97, 48, 74, 66] >>>> Debemos cambiar 97 por 48
[48, 97, 74, 66], —> i = 0, v = 48
[48, 97, 74, 66], —> i = 1, v = 48 Debemos cambiar 97 por 74
[48, 74, 97, 66], —> i = 0, v = 74
[48, 74, 97, 66], —> i = 1, v = 74
[48, 74, 97, 66], —> i = 2, v = 74 Debemos cambiar 97 por 66
[48, 74, 66, 97], —> i = 1, v = 66 Debemos cambiar 74 por 66
[48, 66, 74, 97], —> i = 0, v = 66
[48, 66, 74, 97], —> i = 1, v = 66
[48, 66, 74, 97], —> i = 2, v = 66
[48, 66, 74, 97], —> i = 3, v = 66
Ordenada: <<<<<<<<<<<<<<<<<<<<<<< [48, 66, 74, 97] >>>>>>>>>>>>>>>>>>>>>>>>>>
import random def orden_por_insercion(o): a = len(o) v = 0 i = 0 while i < a - 1: if o[i] > o [i+1]: print(f'Debemos cambiar {o[i]} por {o[i+1]} \n') v = o[i+1] #intercambio 2 datos con 3 lineas o[i+1] = o[i] o[i] = v if i > 0: i = i - 1 else: i = i + 1 print('') print(f'{(o)}, ---> i = {i}, v = {v}') return o if __name__ == '__main__': t = int(input(' Digite tamaño de lista: ')) o = [random.randint(0,100) for i in range(t)] print(f' Su lista es <<<< {(o)} >>>>') o = orden_por_insercion(o) print(f'\n Ordenada: \n <<<<<<<<<<<<<<<<<<<<<<< {o} >>>>>>>>>>>>>>>>>>>>>>>>>>')```
Interesante, pero los nombres de tus variables confunden.
Bastante creativo.
Ya quedó el artículo publicado.
Tengo una pregunta: No pude resolver este ejercicio sin antes ver la explicacion y el algorotmo explicado por pyrhon tuthor. ¿Quiere decir eso que soy malo para programar? No entendí tan bien el problema y se me fue dificil porgramarlo. ¿Dónde puedo praticar mas de estos ejercicios para incrementar mi power? ayuda :'v :(
Hola Clayton, no creo que seas malo para programar. Creo que eres una persona que con la ayuda visual, como Python Tutor (herramienta que no conocía y me pareció uffff genial, gracias por ello😉) le va mejor. Aquí lo importante es que identificaste algo que te ayuda a aprender mejor. En mi caso me ayudo con videos en you tube que expliquen con animaciones, lo que también una ayuda visual. Cada quien tiene su estilo y eso no lo hace mejor o peor programador. Lo que te va a ayudar a ser mejor es estudiar más, investigar, practicar, y nunca parar de aprender 💚
Este es mi código, antes de ver el del profesor:
def ordenamiento_insercion(lista): iteraciones = 0 for i in range(1,len(lista)): j = i while lista[j] < lista[j-1] and j > 0: lista[j],lista[j-1] = lista[j-1],lista[j] j -= 1 # print(lista) iteraciones +=1 return lista,iteraciones
La variable iteraciones, me permite guardar cuantas iteraciones hace el código para compararlo con el ordenamiento de burbuja
Aquí mi código, con los comentarios traté de darle mas sentido :)
import random #Importa la libreria para poder generar numeros aleatoreos def ordenamiento_insercion(lista): for i in range(1, len(lista)): # Itera cada indice de la lista, comenzando de la posición '1' y no en la posición '0' ya que esta contiene el primer valor de nuestra 'nueva sublista ordenada' valor_actual = lista[i] # Aquí se obtiene el valor con el que hacemos la comparación, para luego insertarlo en la posición ordenada que le corresponde posicion_actual = i # Entiendo que esta asignación no es necesaria pero facilita el entendimiento # Se podría remplazar posicion_actual por 'i' while posicion_actual > 0 and lista[posicion_actual - 1] > valor_actual: # La primera condición evita un bucle infinito, la segunda condición evalua si el valor de la posición evaluada es menor respecto al valor de la posición anterior, la evaluacion se hace de izquierda a derecha lista[posicion_actual] = lista[posicion_actual - 1] # Aqui se insertan los valores con los que evaluamos, la reasignacion es hacia la izquierda i -= 1 # Con esto aseguramos que la evaluacion se haga con la posicion anterior lista[posicion_actual] = valor_actual # Finalmente inseramos el valor que tomamos en la posicion que corresponde return lista if __name__=='__main__': tamano_lista = int(input('De que tamano sera la lista? ')) # Inserta tamaño de lista lista = [random.randint(0,100) for i in range(tamano_lista)] # Crea la lista con valores aleatoreos print(lista) # Imprime lista lista_ordenada = ordenamiento_insercion(lista) # Invoca la función de ordenamiento de lista por insercion print(lista_ordenada) # Imprime la lista ordenada```
Genial, muchas gracias, tenia un error y me ayudaste a solucionarlo!
Me costó un poquito, pero salió al final
import random def ordenamiento_por_insercion(lista): for i in range(1, len(lista)): valor_actual = lista[i] pos = i while pos > 0 and lista[pos - 1] > valor_actual: lista[pos], lista[pos - 1] = lista[pos - 1], lista[pos] pos -= 1 lista[pos] = valor_actual return lista if __name__ == '__main__': tamano_lista = int(input('Digite el tamaño de la lista: ')) lista = [random.randint(0,100) for i in range(tamano_lista)] print(ordenamiento_por_insercion(lista))```
Tal vez les interese ver este y otros varios algoritmos de ordenamiento gráficamente.:
