Ordenamiento por inserci贸n

18/25

Lectura

Ordenamiento por inserci贸n

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 鈥渟u
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

Aportes 246

Preguntas 1

Ordenar por:

驴Quieres ver m谩s aportes, preguntas y respuestas de la comunidad? Crea una cuenta o inicia sesi贸n.

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

Si no entendieron del todo el c贸digo (como me paso a mi) pueden ver este video, la verdad me ayudo much铆simo a entender este algoritmo.
https://www.youtube.com/watch?v=P05_0zUxJTQ

Comparto una imagen, para una aquellos compa帽eros que le gusta ver la cosas de manera grafica.

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()

Hola si les est谩 costando entender este algoritmo aqu铆 les dejo dos video que ayudan bastante a entenderlo. Saludos.

  1. Explicaci贸n del algor铆tmo:
    https://www.youtube.com/watch?v=bB8Px8D9QdQ

  2. Implementaci贸n del algor铆tmo:
    https://www.youtube.com/watch?v=PUudQLFI8bA

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)```
<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)

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 esten 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)```

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

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帽ol

**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}   >>>>>>>>>>>>>>>>>>>>>>>>>>')```

Bueno a mi me gusta programar en ingl茅s para que el c贸digo no parezca spanglish, no me juzguen ja, ja!

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```

Insertion sort: Este algoritmo es como arreglar las cartas que tienes en tu mano, por ejemplo:

Vez la primera carta que tienes que es 鈥淴鈥, y esa la vas a cambiar por la posicion de la siguiente carta que es 鈥淵鈥 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.

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.:

https://visualgo.net/en/sorting

Ac谩 un libro gratuito sobre algoritmos en PDF. URL

Comparto mi c贸digo 馃槃! Lo hice solo observando la explicaci贸n y sugiero hacer lo mismo para interiorizar el concepto del algoritmo 馃槃!

def insertion_process(lista,lenght_list):
    for i in range(lenght_list):
        position = int(input("Ingrese el {}) elemento de la lista: ".format(i+1)))
        lista.append(position) 
    for j in range(lenght_list):
        for i in range(lenght_list - j - 1): 
            if lista[i] > lista [i+1]:
                valor_actual = lista[i+1]
                lista[i+1] = lista[i]
                lista[i] = valor_actual
    return print(lista)    
    

if __name__ == "__main__":
    lenght_list = int(input("驴Qu茅 tama帽o tendr谩 la lista?"))
    lista = []
    insertion_process(lista,lenght_list)

por si es que no quedo claro:
https://www.youtube.com/watch?v=bB8Px8D9QdQ

Encontr茅 este tutorial que explica el algoritmo y lo implementa. Est谩 en idioma ingl茅s:
Video de Derrick Sherrill

Para lo que no logran entender este c贸digo te muestra el progreso de cada variable, si se cumple la sentencia while y el progreso de la lista con cada iteraci贸n

import random
import time
def ordenamiento_por_insercion(lista,_iter = 0,_subiter = 0):

    for indice in range(1, len(lista)):
        _iter += 1
        valor_actual = lista[indice] 
        print(f'______________________________________________________________')
        print(f'Valor_actual en la iteracion {_iter} = {valor_actual}')
        posicion_actual = indice
        print(f'Posicion_actual en la iteracion {_iter} = {posicion_actual}')
        print(f'______________________________________________________________')
        
        while posicion_actual > 0 and lista[posicion_actual - 1] > valor_actual:
            _subiter += 1
           
            print(f'iteracion {_iter}, subiteracion {_subiter} = True')
            lista[posicion_actual] = lista[posicion_actual - 1]
            print(lista[posicion_actual])
            print(lista[posicion_actual - 1])
            print(lista)
            posicion_actual -= 1
           
            

        lista[posicion_actual] = valor_actual
        print(lista)
        _subiter = 0
    return lista


if __name__ == "__main__":
    user_range = int(input('Escotge la longitud de tu lista: '))
    start = time.time()
    lista = [random.randint(0,10) for i in range(user_range)]
    end = time.time()
    duration = (end - start)

    print(f'Lista a ordenar: {lista}')
    lista_ordenada = (ordenamiento_por_insercion(lista))
    print(f'Lista ordenada: {lista_ordenada}')
    print(f'Lista ordenada en {duration}s')


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 馃槮

import random 

def ordenamiento_por_insercion(lista):
    for i in range(1, len(lista)):
        valor_actual = lista[i]
        posicion_actual = i

        while posicion_actual > 0 and lista[posicion_actual - 1] > valor_actual:
            lista[posicion_actual] = lista[posicion_actual -1]
            posicion_actual -= 1
            print(f'ORDENANDO LISTA  : {lista}')
        lista[posicion_actual] = valor_actual
    return lista

if __name__ == '__main__':
    longitud_lista = int(input('Longitud de la lista: '))
    lista = [random.randint(1, 100) for i in range(longitud_lista)]
    print(f'LISTA DESORDENADA: {lista}')

    lista_ordenada = ordenamiento_por_insercion(lista)
    print(f'LISTA ORDENADA   : {lista_ordenada}')```

:,v me siento como el programador que no entiende lo que hizo pero funciona :,3

import random
longitud = int(input("Ingresa la longitud de la lista: "))

lista = [random.randint(0, 100) for x in range(longitud)]

for i in range(0, len(lista)):
    print(lista) 
    for j in range(0, len(lista)-1):
        if lista[i]  < lista[j] and i != j: # si ponen mayor que, se ordenan de manera descendente
            # y si se pone < se ordenan ascendente
            print(f"Parece que tenemos que cambiar {lista[i]}, por {lista[j]}")
            lista[i] , lista[j] = lista[j], lista[i]

print(lista)

Aunque aun no entienda al 100% y me cueste mucho, lo intento y este fue el resultado 馃槃

SI indice empieza con el valor de 1 , el valor_actual no tomaria el primer valor de la lista sino el segundo,
tengo esa gran duda

Ya qued贸 el art铆culo publicado.

El cdigo fue el siguiente:

import random

def ordenamiento_por_insercion(lista):
    n = len(lista)
    
    for i in range(1, n):
        valor_actual = lista[i]
        posicion_actual = i

        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(valor_actual)

    return lista    

if __name__ == '__main__':
    
    tamano_lista = int(input('De que tama帽o quieres la lista?: '))
    lista = [random.randint(0, 100) for i in range(tamano_lista)]

    print(lista)

    lista_ordenada = ordenamiento_por_insercion(lista)
    print(lista_ordenada)

"""Ordenamiento por insercion."""

import random


def ordenamiento_insercion(lista):
    n = len(lista)

    for i in range(1, n):
        valor_actual = lista[i]
        indice = i

        while indice > 0 and valor_actual < lista[indice -1]:
            lista[indice] = lista[indice -1]
            lista[indice -1] = valor_actual
            indice -= 1

    return lista


if __name__ == "__main__":
    tamano_de_lista = int(input('De que tama帽o sera la lista? '))
    u_lista = [random.randint(0, 100) for i in range(tamano_de_lista)]
    print(u_lista)

    o_lista = ordenamiento_insercion(u_lista)
    print(o_lista)

Hay que a帽adir la l铆nea de c贸digo 鈥榬eturn lista鈥 si no la funciomn no retorna nada

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
    return lista

Le agregue un contador del numero de iteraciones que necesita hasta tener la lista ordenada

import random

def ordenamiento_inseccion(lista, nro_iter=0):
    
    for indice in range(0, len(lista)):
        
        valor_actual = lista[indice]
        posicion_actual = indice

        while posicion_actual > 0 and lista[posicion_actual - 1] > valor_actual:
            nro_iter +=1
            lista[posicion_actual] = lista[posicion_actual - 1]
            posicion_actual -= 1

        lista[posicion_actual] = valor_actual

    return(lista, nro_iter)

if __name__ == '__main__':
    tamano_de_lista = int(input('De que tama帽o es la lista? '))
    
    lista = ([random.randint(0, 100) for i in range(tamano_de_lista)])
    print (lista)

    (lista_ordenada,nro_iter) = ordenamiento_inseccion(lista)
    print(lista_ordenada)
    print(f'el numero de iteracciones son: {nro_iter}')```

Les comparto mi c贸digo para ordenamiento por inserci贸n:

def ordenamiento_por_insercion(lista):
    n = len(lista)
    for i in range(1, n):
        valor_actual = lista[i]
        for j in range(i, 0, -1):
            if valor_actual > lista[j-1]:
                break
            else:
                lista[j], lista[j-1] = lista[j-1], lista[j]

    return lista
import random

def ordenar_insercion(lista):

    n = len(lista)
    
    for i in range(1, n):
        for j in reversed(range(i)):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
            else:
                break
    return lista

import random
import time 

def ordenamiento_de_burbuja(lista):
    n = len(lista)
    pasos = 0

    for indice in range(1, n):
        valor_actual = lista[indice]
        posicion_actual = indice

        while posicion_actual > 0 and lista[posicion_actual - 1] > valor_actual:
            pasos += 1
            lista[posicion_actual] = lista[posicion_actual - 1]
            posicion_actual -= 1

        lista[posicion_actual] = valor_actual

    print(f'Se necesito {pasos} itereaciones.\n')
    return lista



def run():
    while True:

        tamano_de_lista = int(input('Indique el tama帽o de la lista:  '))
        lista = [random.randint(0,tamano_de_lista) for i in range(tamano_de_lista)]
        print(lista)
        principio = time.time()
        lista_ordenada = ordenamiento_de_burbuja(lista)
        fin = time.time()
        tiempo = fin- principio
        print(lista_ordenada)
        print(f'Me demore: {tiempo} segundos ordenando la lista')


if __name__ == "__main__":
    run()

Mi soluci贸n para este tipo de ordenamiento:

import random

def ordenamiento_de_insercion(lista):
    n = len(lista)
    
    for i in range(0, n - 1):
        contador = i
        while contador < n:
            
            if  lista[i] > lista [contador]:
                valor_actual = lista[i]
                lista.pop(i)
                lista.append(valor_actual)
                contador = i
            contador += 1
    return lista

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_de_insercion(lista)
    print(lista_ordenada)

Lo interesante de este ejercicio es todas las formas en las que pudimos resolver este ejercicio, aqu铆 les comparto el c贸mo lo resolv铆:


lista = [7,3,2,9,8,8,2,5,4,3,6,8,6,3,3,5,7,9,4,3,0,1]
lista_ordenada = []

def orden_por_insercion(lista):

    for i in range(len(lista)):

        if i != 0:

            for j in range(len(lista_ordenada)):

                if lista[i] <= lista_ordenada[j]:

                    lista_ordenada.insert(j, lista[i])
                    break

                elif j == len(lista_ordenada) - 1:

                    lista_ordenada.insert(j + 1, lista[i])

        else:

            lista_ordenada.insert(0,lista[0])
        
    return lista_ordenada


if __name__ == "__main__":

    print(orden_por_insercion(lista))

Ejemplo Insertion sort Python:

lista = [5, 10, 3, 7, 4, 2, 6, 1, 9]

for i in range(1, len(lista)):

#Empezamos con el indice 1, por que el numero que empecemos agarremos como indice o que lo pasemos en una sub lista va a ser comparado con los valores que se encuentran a la izquierda

    actual = lista[i] #Este es el numero que se va a ir a la sublista
    indice = i #Este es el numero que le vamos a hacer la comparacion, este es el indice de partida en la direccion de la izquierda

    while indice > 0 and lista[indice - 1] > actual:
        
        lista[indice] = lista[indice - 1] #Con esto vamos a disminuir el valor, hasta llegar al menor de la lista para colocarlo antes de su posicion
            indice = indice - 1 #En este momento evaluamos de nuevo la condicion del bucle while, para seguir recorriendo la lista

    lista[indice] = actual #Insertamos en esta lista el elemento que teniamos guardado en la variable actual o en nuestra sublista

print(lista)

As铆 se me ocurri贸 antes de ver el c贸digo del post. A mi parecer son en esencia lo mismo, s贸lo que ac谩 uso el comando para intercambiar variables aprendido en una clase anterior, en vez de usar una variable extra para almacenarlas.

def insertion_sort(lista):
    for i in range(1,len(lista)):
        for j in range(i):
            if lista[i - j] < lista[i - j - 1]:
                lista[i - j], lista[i - j - 1] = lista[ i - j - 1], lista[i - j]
    return lista```
## Alfonso Garijo Campos

import random

def insertion_ordering(disordered, verbose):
    ordered = []
    bigger = False

    for i in range(len(disordered)):
        actual = disordered[0]
        disordered.pop(0)

        if(i == 0):
            ordered.append(actual)
        else:
            for j in range(len(ordered)-1, -1, -1):
                if(ordered[j] < actual):
                    ordered.insert(j+1,actual)
                    bigger = True
                    break
            if(bigger == False):
                ordered.insert(0, actual)
            else:
                bigger = False
        #print("iteration: ",i+1,"\nOrdered =", ordered,"\nDisordered =", disordered,"\n")
        if(verbose):
            print("iteration: ",i+1,"\nOrdered =", ordered,"\n")
    return(ordered)

if __name__ == '__main__':
    N = int(input("\nHow long would you like the disordered list to be?: "))
    created_list = random.sample(range(0, N*10), N)
    print("\nThis is the created list:\n",created_list)
    result = insertion_ordering(created_list, False)
    print("\nThe created list has been ordered:\n",result)

Les comparto mi codigo. probando varias veces podemos destacar que la complejidad algor铆tmica puede ir de O(n -1) en el mejor de los casos, hasta n**n/4 o un poco mas en el peor, a lo mejor falto mas testeo para determinar bien el peor

Mi Codigo

def ordernamiento_por_insercion(lista):
    step = 0
    lista_ordenada = [lista[0]]
    lista.pop(0)
    for elemento in lista:
        tamano_de_lo = len(lista_ordenada)
        for posicion in range(tamano_de_lo):
            step += 1 
            #print(lista_ordenada[0:posicion + 1])
            if elemento <= lista_ordenada[posicion]:
                elemento_tope = lista_ordenada[posicion]
                lista_ordenada[posicion] = elemento
                lista_ordenada.insert(posicion + 1, elemento_tope)
                break

            elif posicion == (tamano_de_lo - 1):
                lista_ordenada.insert(posicion + 1, elemento)

    return (lista_ordenada, step)

CODIGO:

import random

def sort_insercion(lista):
  for i in range(len(lista)):
    for j in range(i,0,-1):
      if lista[j-1] > lista[j] :
        auxiliar = lista[j]
        lista[j] = lista[j-1]
        lista[j-1] = auxiliar
  print(lista)

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)
    sort_insercion(lista)

EJECUCION:
De que tamano sera la lista? 20
[73, 34, 69, 20, 28, 13, 32, 50, 47, 66, 50, 43, 32, 100, 77, 95, 45, 89, 83, 1]
[1, 13, 20, 28, 32, 32, 34, 43, 45, 47, 50, 50, 66, 69, 73, 77, 83, 89, 95, 100]

Inicialmente la construcci贸n del agloritmo en el resultado no era el indicado y con un poco de ayuda en internet logre hacerlo de una forma corta pero con el resultado q se quiere.

import random

def ordenamiento_inserccion(lista):
    n = len(lista)

    for i in range(0, n):
        while i > 0:
            if lista[i - 1] > lista[i]:
                lista[i], lista[i - 1] = lista[i - 1], lista[i] #swapping

            i = i - 1                
    
    return lista

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(f'Lista inicial en desorden: {lista}')

    lista_ordenada = ordenamiento_inserccion(lista)
    print(f'Lista en orden: {lista_ordenada}')

Resultado:
Lista inicial en desorden: [53, 5, 16, 54, 39, 14, 64, 100, 69, 62]
Lista en orden: [5, 14, 16, 39, 53, 54, 62, 64, 69, 100]

Les dejo mi soluci贸n:

import random

def ordenamiento_insercion(lista):
    largo = len(lista) 

    for i in range(1, largo): 
        valor_actual = lista[i]  
        j = i - 1 

        while j >= 0 and lista[j] > valor_actual:
            lista[j+1] = lista[j] 
            j -= 1 
            print(lista)

        lista[j + 1] = valor_actual 
    
    return lista
        
if __name__ == '__main__':
    tamano_lista  = int(input('De que tama帽o sera la lista? '))

    lista = [random.randint(0, 100) for i in range(tamano_lista)]
    print(lista)

    lista_ordenada = ordenamiento_insercion(lista)
    print(lista)

Creo que la complique m谩s de lo necesario pero ahi va:

import random

def ordenamiento_insercion(lista):
    lista_ordenada = []
    lista_ordenada_variable =[]
    lista_ordenada.append(lista[0])
    for i in range(1,len(lista)):
        lista_variable= lista_ordenada[:]
        mov = 1
        paso = i
        print(i)
        print(f'LISTA ITERABLE {lista_variable}')
        for item in lista_ordenada[::-1]:
            print(f'El item {item}')
            print(f'El valor actual: {lista[i]}')
            if  lista[i]<item :
                
                if mov>1:
                    lista_ordenada.insert(i-mov,lista_ordenada.pop(paso)) 
                else:
                    lista_ordenada.insert(i-mov,lista[i]) 

            elif lista[i]>=item and mov ==1:
               lista_ordenada.append(lista[i])
               break 
            elif lista[i]>=item and mov >1:
               break
            print(f'Resultado {lista_ordenada}') 
            paso=i-mov
            mov+=1 
              
    return lista_ordenada

if __name__ == '__main__':
    tama帽o_de_lista = int(input('De que tama帽o ser谩 la lista? '))
    lista = [random.randint(0,100) for i in range(tama帽o_de_lista)]
    print(lista)
    lista_resultado = ordenamiento_insercion(lista)
    print(f'lista inicial: {lista}') 
    print(f'Lista ordenada: {lista_resultado}')

Aqu铆 les dejo mi aporte del m茅todo

def ordenamiento_insercion(lista):
    n = len(lista)

    for i in range(1, n):
        actual = lista[i]
        for j in range(i, 0, -1):
          elemento2 = lista[j-1]
          if elemento2 > actual:
            lista[j] = elemento2
            lista[j-1] = actual
    return lista```

Aqui va la pr谩ctica de la clase:

import random

def ordenamiento_de_burbuja(lista):
    
    n = len(lista)

    for i in range(n):
        valor_actual = lista[i]
        posicion_actual = i

        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(lista)
        
    return lista
                
if __name__ == "__main__":
    tamano_de_lista = int(input('De que atamno sera la lista? '))

    lista = [random.randint(0, 100) for i  in range(tamano_de_lista)]
    print(lista)

    lista_ordenada = ordenamiento_de_burbuja(lista)
    print(lista_ordenada)

Considero que el algoritmo de ordenaci贸n por inserci贸n y el de burbuja, son iguales en rendimiento. Tienen un Big O igual. Aqu铆 dejo el c贸digo con el que lo pruebo.

from random import randint

def ordenamiento_de_burbuja(lista, pasos):
    n = len(lista)

    for i in range(n):

        for j in range(0, n -i -1):
            
            if lista[j] > lista[j + 1]:
                pasos += 1
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
                

    return lista, pasos

def ordenamiento_por_insercion(lista, pasos):

    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
            pasos += 1

        lista[posicion_actual] = valor_actual
        

    return lista, pasos

tamanio = int(input('ingrese el tama帽o de la lista: '))

lista_1 = [randint(0, 100) for i in range(tamanio)]
lista_2 = lista_1[::]
pasos_1 = 0
pasos_2 = 0

print(lista_1)
print(lista_2)

lista_ordenada_1, pasos_1 = ordenamiento_de_burbuja(lista_1, pasos_1)
lista_ordenada_2, pasos_2 = ordenamiento_por_insercion(lista_2, pasos_2)

print(f'Son {pasos_1} del ordenamiento de burbuja')
print(f'Son {pasos_2} del ordenamiento por insercion')

Y los art铆culos ?

import random
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
    return print(lista)

if __name__=="__main__":
    tamano_de_la_lista = int (input('De que tamano sera la lista?  '))
    lista= [random.randint(0,100) for i in range(tamano_de_la_lista)]
    print(lista)

    lista_ordenada=ordenamiento_por_insercion(lista)```

Para verlo un poquito mas grafico
https://www.youtube.com/watch?v=OGzPmgsI-pQ

def ordenamiento(lista):
    n = len(lista)
    lista_o = [lista[0]]
    for i in range(1,n):
        
        lista_o.append(lista[i])
        m = len(lista_o)
        
        for j in range(m-1,0,-1):
            if lista_o[j] < lista_o[j - 1]:
                lista_o[j-1],lista_o[j] = lista_o[j], lista_o[j-1]  
    return lista_o

from random import randint

def ord_insercion(lista):
    for i in range(1, len(lista)):
        valor_actual = lista[i]
        pos_actual = i
        while pos_actual > 0 and valor_actual < lista[pos_actual - 1]:
            lista[pos_actual] = lista[pos_actual - 1]
            lista[pos_actual-1] = valor_actual
            pos_actual -= 1
        print(f"{lista}, valor actual = {valor_actual}")
    return lista

if __name__ == '__main__':
    lista = [randint(0,10) for i in range(10)]
    print(lista)
    lista = ord_insercion(lista)
    print(lista)

en la consola sale algo as铆:

[3, 5, 7, 7, 8, 1, 6, 7, 7, 6]
[3, 5, 7, 7, 8, 1, 6, 7, 7, 6], valor actual = 5
[3, 5, 7, 7, 8, 1, 6, 7, 7, 6], valor actual = 7
[3, 5, 7, 7, 8, 1, 6, 7, 7, 6], valor actual = 7
[3, 5, 7, 7, 8, 1, 6, 7, 7, 6], valor actual = 8
[1, 3, 5, 7, 7, 8, 6, 7, 7, 6], valor actual = 1
[1, 3, 5, 6, 7, 7, 8, 7, 7, 6], valor actual = 6
[1, 3, 5, 6, 7, 7, 7, 8, 7, 6], valor actual = 7
[1, 3, 5, 6, 7, 7, 7, 7, 8, 6], valor actual = 7
[1, 3, 5, 6, 6, 7, 7, 7, 7, 8], valor actual = 6
[1, 3, 5, 6, 6, 7, 7, 7, 7, 8]

Mi implementaci贸n del Insertion Sort: 馃
.

import random

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

    return lista

if __name__ == '__main__':
    print('\n')
    tamano_de_lista = int(input('Inserta el tamano de la lista '))
    print('\n')
    lista = [random.randint(0, 100) for i in range(tamano_de_lista)]
    print(lista)
    print('\n')
    lista_ordenada = ordenamiento_por_insercion(lista)
    print(lista_ordenada)```

Muy interesante el m茅todo de ordenamiento por inserci贸n, todav铆a no entiendo al 100 las clases de complejidad algor铆tmica pero yo creo que la clase que se esta usando es la de n Log n.

Hola les presento mi c贸digo, tienen ayuda visual del print statement.

import random

def ordenamiento_insercion(lista):
    for i in range(1, len(lista)):
        valor_actual = lista[i]
        i = i

        while i > 0 and lista[i - 1] > valor_actual:
            lista[i] = lista[i - 1]
            i -= 1
            print(f'Verificamos que {valor_actual} es menor que {lista[i]}, por lo que movemos {lista[i]} un lugar a la derecha')

        lista[i] = valor_actual
        print(f'Verificamos que no hay un numero a la izquierda mas grande que {lista[i]} por lo que toma directamente su posici贸n.')
    return lista

if __name__ == '__main__':
    tamano_de_lista = int(input('cuantos caracteres quieres?'))

    lista = [random.randint(0, 100) for i in range(tamano_de_lista)]
    print(lista)

    lista_ordenada = ordenamiento_insercion(lista)
    print(lista_ordenada)```

me cuesta trabajo entender, supongo que tengo que comenzar el curso nuevamente.

Me resulta interesante que con bubble sort son los n煤meros mayores los que se mueven al final, esto es obvio, pero digamos que estamos arrastrando todo lo mayor al final, y con insertion sort arrastramos todo lo menor al inicio, es decir, con el primero los n煤meros mayores son los que se mueve mientras que con insertion sort son los menores. Espero que me explique y no parezca una tonter铆a. Jejeje.

Buena info, a ponerla en practica. En el ordenamiento por inserci贸n, a cada paso se considera que los elementos que se encuentran en el segmento de 0 a i est谩n ordenados, de manera que agregar un nuevo elemento implica colocarlo en la posici贸n correspondiente y el segmento seguir谩 ordenado.

Este es mi logaritmo de ordenamiento por inserci贸n:

def ordenamiento_insercion(lista):
        
    for i in range(1,len(lista)):        
        while  i>=1 and i-1>=0 and lista[i]<lista[i-1]:
            lista[i],lista[i-1] = lista[i-1], lista[i] 
            i-=1               
    return lista  

Asi queda el codigo ya para probarlo en la terminal

import random

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

    return lista

if __name__ == "__main__":
    tamano_de_la_lista = int(input('De que tamano es la lista?  '))

    lista = [random.randint(0,100) for i in range(tamano_de_la_lista)]
    print(lista)
    
    lista_ordenada = ordenamiento_por_insercion(lista)
    print(lista_ordenada)

Esta es la forma en la que implemente el algoritmo, agregue un contador para saber cuantas veces itera el ciclo.

import random
def ordenamiento_por_insercion(lista):

    contador = 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:
            contador += 1
            lista[posicion_actual] = lista[posicion_actual - 1]
            posicion_actual -= 1

        lista[posicion_actual] = valor_actual
    print(contador)
    return lista


if __name__ == '__main__':
    tama帽o_de_lista = int(input('De que tama帽o sera la lista? '))

    lista = [random.randint(0, 100) for i in range(tama帽o_de_lista)]
    print(lista)

    lista_ordenada = ordenamiento_por_insercion(lista)
    print(lista_ordenada)```
import random


def insert_sort(unordered_list) -> list:
    for index in range(0, len(unordered_list)):
        actual_valor = unordered_list[index]
        actual_position = index

        while (actual_position > 0
               and unordered_list[actual_position - 1] > actual_valor):
            unordered_list[actual_position] = unordered_list[actual_position - 1]
            actual_position -= 1

        unordered_list[actual_position] = actual_valor
    return unordered_list


if __name__ == '__main__':
    len_of_list = int(input('what is the len of the list?'))
    unordered_list = [random.randint(0, 100) for i in range(len_of_list)]
    print(unordered_list)

    sorted_list = insert_sort(unordered_list)

    print(sorted_list)

Me tarde varias horas programando, pero porfin se armo. Este codigo funciona al 100% para cualquier tama帽o de lista con enteros positivos y negativos, decimales y fracciones.

# import math ...si es que se requieren raices cuadradas, o pi ...ejemplo: math.sqrt() o math.pi



numeros=[0,2,3,-7/4,3.2232323]    #<--------- si se quiere ordenar decimales, negativos o integers
#numeros=[int(x) for x in input('Introducir lista ').split()]  #<--- si se quiere introducir integers







sublistaOrdenada=[numeros[0]]
sublistaNoOrdenada=numeros[1:len(numeros)]



for i in range(len(numeros)-1):
    sublistaOrdenada.append(sublistaNoOrdenada[i]) #append agrega el ultimo valor del argumento a la variable antes del .
    
   
    if sublistaOrdenada[i]>sublistaOrdenada[i+1]:
        sublistaOrdenada[i],sublistaOrdenada[i+1]=sublistaOrdenada[i+1],sublistaOrdenada[i]

    

for i in range(len(numeros)-1):
    if sublistaOrdenada[(len(numeros)-1)-i]>sublistaOrdenada[(len(numeros)-1)-i-1]:
        pass
    else:
        sublistaOrdenada[(len(numeros)-1)-i],sublistaOrdenada[(len(numeros)-1)-i-1]=sublistaOrdenada[(len(numeros)-1)-i-1],sublistaOrdenada[(len(numeros)-1)-i]
print('---------------------------------------')
print('El arreglo de numeros a arreglar es:')
print (numeros)
print('---------------------------------------')
print('El ordenamiento por insercion arroja:  ')
print (sublistaOrdenada)
print('---------------------------------------')

Cual es el proposito de poner en el while la condicion posicion_actual > 0, si posicion actual es siempre mayor a cero?

Mine

def select_sort(number):

    for i in range(len(number)):
        print(number)
        for j in range(i+1, len(number)):
            if number[i] > number[j]:
                temp = number[i]
                number[i] = number[j]
                number[j] = temp
    return number

if __name__ == '__main__':
    numbers = [6,8,5,8,77,22,54,8,5,8,5,84,8,181,0]
    ol_munbers = select_sort(numbers)

Lo logr茅!!! :

def insercion(lista):
    n = len(lista)
    for i in range(1, n):
        valor_actual = lista[i]
        j = i
        while j > 0:
            if lista[j] < lista[j - 1]:
                lista[j] = lista[j - 1]
                lista[j - 1] = valor_actual
            j -= 1       
    return lista

if __name__ == '__main__':
    tamano_de_lista = int(input('De que tama帽o es la lista? '))
    lista = []
    for i in range(tamano_de_lista):
        lista.append(random.randint(0,100))
    lista_ordenada = []
    print(lista)
    lista_ordenada = insercion(lista)
    print(lista_ordenada)

si lista es un vector como lista = [1,98,2,78,74] pueden usar, para facilitar la lectura al usar range y hacer el corrimiento por posici贸n al usar len

for elemento in lista:
print(elemento)

Explicaci贸n Gr谩fica:

Hice un video para explicarlo gr谩ficamente, espero les sirva:

https://youtu.be/UU0cAwjl9UM

#ALGORITMOS DE ORDENAMIENTO

if __name__ =="__main__":
    lista = [6 , 5 , 3 , 1 , 8 , 7 , 2 , 4]
    #lista = []
    l = len(lista)
    for i in range(1, l):
        #Tomo el elemento element de la lista (primero de la lista desordenada)
        element = lista[i]
        print(f"iteracion nro {i}")
        print(f" elemento a ordenar : {element}")
        print("sublista ya ordenada: ", lista[0:i:])
        # si el primer elemento de la lista desordenada es menor que el 
        # #ultimo elemento de la lista ordenada, debo reordenar
        if element < lista[i-1]:
            print("debo reordenar")

            # trato de ubicar el element dentro de la lista ordenada
            for j in range(0,i):
                print(f"comparo {element} con {lista[j]}")
                #voy buscando el lugar correcto para element
                #si element es mayor que el lista[j] sigo adelante
                print(f"elementpo {j} de la lista ordenada:")
                if element > lista[j]:
                    print(f"{element} es mayor que {lista[j]} paso al siguiente elemento")
                else: #cuando llego a un lista[j] que es mayor a element, alli deberia ubicarlo
                    # y el resto de la lista ordenada correrla un lugar hacia la derecha
                    print(f"{element} es menor que {lista[j]}")
                    print(f"debo ubicar {element} en el lugar {j}")
                    index = i
                    while index > j:
                        lista[index] = lista[index -1] 
                        index  = index - 1
                    lista[j] = element
                    break
        #si el element es mayor que el ultimo elemento de la lista ordenada sigo adelante
        else:
            print("no debo reordenar")
            next
    print(lista)

Mi implementaci贸n del algoritmo:))

def insertion_sort(arr):
    for i in range(1, len(arr)):
        curr_value = arr[i]

        for j in range (i-1, -1, -1):
            if curr_value < arr[j]:
                arr[j+1] = arr[j]

                if j == 0:
                    arr[j] = curr_value
            elif curr_value > arr[j]:
                arr[j+1] = curr_value
                break

    return arr

[AQU脥]((https://www.youtube.com/watch?v=P05_0zUxJTQ) est谩 explicado muy b谩sicamente como funciona

Me cost贸 lograrlo por mi mismo 馃槮
Ahora a ver la soluci贸n.

import random

def ord_insercion(lista):
    orden = []
    orden.append(lista[0])
    for elemento in lista[1::]:  
        if elemento <= orden[0]:
            orden.insert(0, elemento)
        else:
            for i in range(len(orden)):
                if orden[i] < elemento and i != len(orden)-1:
                    continue
                elif orden[i] >= elemento:
                    orden.insert(i,elemento)
                    break
                else:
                    orden.append(elemento)        
    return orden                

if __name__ == '__main__':
    list_size = int(input('De que tama帽o va querer la lista? '))
    lista = [random.randint(0, 100) for i in range(list_size)]
    print(lista)
    lista_ordenada = ord_insercion(lista)
    print(lista_ordenada)

Este es el codigo que hice:

from random import randint

def ordenamiento_insercion(lista):
    for i in range(1, len(lista)):
        actual = lista[i]
        indice = i

        while indice > 0 and lista[indice -1] > actual:
            lista[indice] = lista[indice -1]
            indice -= 1

        lista[indice] = actual
        print(lista)
    return lista

if __name__ == '__main__':                
    tamano_de_lista = int(input('De que tamano sera la lista? '))

    lista = [randint(0, 100) for i in range(tamano_de_lista)]
    print(lista)

    lista_ordenada = ordenamiento_insercion(lista)
    print('Lista ordenada:')
    print(lista_ordenada)
from random import randint

def sort_list(lst):
    
    sorted_list = []
    sorted_list.append(lst[-1])
    print(f'Taking {lst[-1]} as base')
    lst.remove(lst[-1])
    list_length = len(lst)

    for i in range(list_length):

        if max(sorted_list) <= lst[-1]:
            print(f'Inserting at the end with length {len(sorted_list)} > {lst[-1]}')
            sorted_list.append(lst[-1])
        elif min(sorted_list) >= lst[-1]:
            print(f'Inserting at the begining with length {len(sorted_list)} > {lst[-1]}')
            sorted_list.insert(0,lst[-1])
        else:
            j = 1
            while sorted_list[j] < lst[-1]:
                j += 1
            print(f'Inserting element {j} of {len(sorted_list)} > {lst[-1]}')
            sorted_list.insert(j, lst[-1]) 
            
        lst.remove(lst[-1])
    
    return sorted_list



if __name__ == '__main__':
    list_lenght  = int(input('Insert the lenght of your list: '))
    
    list_random  = [randint(0, i) for i in range(list_lenght)]
    print(list_random)

    sorted_list = sort_list(list_random)
    print(sorted_list)

Este es el c贸digo que hice.

Y el output:

Entend铆 el concepto mas por el ejemplo del c贸digo al final que por la descripci贸n del inicio.

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __str__(self):
        return str.format("({},{})", self.x, self.y)

Luego hacemos un ligero cambio en nuestro insertion_sort m茅todo para adaptarse a la clasificaci贸n personalizada:

def insertion_sort(array, compare_function):
    for index in range(1, len(array)):
        currentValue = array[index]
        currentPosition = index

        while currentPosition > 0 and compare_function(array[currentPosition - 1], currentValue):
            array[currentPosition] = array[currentPosition - 1]
            currentPosition = currentPosition - 1

        array[currentPosition] = currentValue
def insertion_sort(array):

    # We start from 1 since the first element is trivially sorted
    for index in range(1, len(array)):
        currentValue = array[index]
        currentPosition = index

        # As long as we haven't reached the beginning and there is an element
        # in our sorted array larger than the one we're trying to insert - move
        # that element to the right
        while currentPosition > 0 and array[currentPosition - 1] > currentValue:
            array[currentPosition] = array[currentPosition -1]
            currentPosition = currentPosition - 1
        array[currentPosition] = currentValue

El ordenamiento por inserci贸n analiza repetidamente la lista de elementos, cada vez insertando el elemento en la secuencia desordenada en su posici贸n correcta.

La principal ventaja de este tipo de ordenamiento es su simplicidad. Tambi茅n exhibe un buen rendimiento cuando se trabaja con una peque帽a lista. El ordenamiento por inserci贸n es un algoritmo de ordenamiento en el lugar, de modo que requiere de espacio m铆nimo. Su desventaja es que no funciona tan bien como otros algoritmos mejores de ordenamiento. Con n al cuadrado pasos requeridos para cada n elemento a ser ordenado, este algoritmo no funciona bien con una lista grande. Por lo tanto, este s贸lo es 煤til cuando se ordena una lista de pocos elementos

  • Mi codigo antes de ver la solucion 馃檭馃檭
import random


def ordenamiento_por_insercion(lista: list):
    lista_ordenada = []
    lista_desordenada = []

    lista_ordenada.append(lista[0])
    lista_desordenada[:] = lista[1:]

    #mientras existan items en la lista desordenada
    while len(lista_desordenada) > 0:
        # tomar la primera posicion
        item_ul = lista_desordenada[0]

        idx_ol = len(lista_ordenada) - 1
        while(item_ul < lista_ordenada[idx_ol] and idx_ol >= 0):
            idx_ol -= 1
        
        # o es mayor el item o llego al indice 0
        if(idx_ol < 0):
            # insertarlo en la primera posicion (es el mas pequeno)
            lista_ordenada.insert(0, lista_desordenada.pop(0))
        else:
            # insertarlo en el idx siguiente al que es mayor o igual
            lista_ordenada.insert(idx_ol+1, lista_desordenada.pop(0))


    return lista_ordenada


if __name__ == "__main__":
    tamano_lista = int(input('De que tamano es la lista: '))

    lista = [random.randint(0, 100) for i in range(tamano_lista)]

    print(lista)
    lista_ordenada = ordenamiento_por_insercion(lista)

    print(lista_ordenada)

Si no entiendes la lectura, copia el c贸digo y ejecutalo con el debuger.

a mi me ayudo un monto, ver el paso a paso del algoritmo.

Les comparto mi resumen
Ordenamiento por inserci贸n (Ins): Por cada elemento de la lista, este se mueve a la derecha hasta que encuentra un elemento menor. Entonces permanece en ese lugar y se contin煤a con el siguiente elemento. As铆 hasta que la lista est茅 ordenada

Ac谩 dejo mi versi贸n, proceder茅 a leer y tratar de entender la que el profesor dejo en la lectura c:

import random

def insertion_sort(list):
    n = len(list)

    for i in range(n - 1):  # List is considered sorted at the beginning
        value = list[i + 1]
        # print(f"---------------\t{value}")
        for j in range(i + 1):  # Comparing with all the values in the left
            # print("sorting")
            if value < list[i - j]:
                list[i - j], list[i - j + 1] = list[i - j + 1], list[i - j]
    return list


if __name__ == '__main__':
    list_size = int(input("Enter the size of the list: "))
    
    list = [random.randint(1, 100) for i in range(list_size)]
    print(list)

    sorted_list = insertion_sort(list)
    print(sorted_list)

Llegu茅 a esto despu茅s de buscar algunos m茅todos
Creo que se lo puede mejorar con una funci贸n de b煤squeda binaria para encontrar el lugar en el cual insertar 鈥渋鈥

import random


def ordenamiento_por_insercion(lista):
    valor_actual = []

    for i in range(1, len(lista)):
        #print(f"i = {i}")
        
        for j in range(i):
            #print(f"j = {j}, valor actual = {valor_actual}")
            if lista[j] > lista[i]:
                valor_actual = [j, lista[i]]
                lista.pop(i)
                lista.insert(valor_actual[0], valor_actual[1])
                break

    return lista

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)
import random


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

    return lista


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)

Ejemplo de c贸digo para el ordenamiento por inserci贸n:

def ordenamiento_por_insercion(lista):
    n = len(lista)
    
    for i in range(1, n):
        a = lista[i]
        
        for j in range (i - 1, -1, -1): 
            if lista[j] > a:
                lista[j + 1] = lista[j]
                
                if j == 0:
                    lista[j] = a

            else:
                lista[j + 1] = a
                break
    
    return lista

Metan print() statements.

O bien utilicen el debugger para tener un mejor visualizaci贸n y por ende un mejor entendimiento del algoritmo.

Aqu铆 esta mi c贸digo con el m茅todo de inserci贸n, adem谩s del de burbuja:

import os
import random

class Ordenamientos:
    
    def __ini__(self):
        pass

    def metodo_burbuja(self, lista):
        self._tamano = len(lista)
        self._index = 1

        for j in range(self._tamano):
            for i in lista:
                if i == lista[0]:
                    self._index = 1
                else:    
                    c = lista[self._index-1]
                    if i < c: 
                        lista[self._index-1] = i
                        lista[self._index] = c
                        self._index += 1
                    else:
                        self._index += 1

        return lista

    def metodo_insercion(self, lista):

        for i in lista:
            
            if i != lista[0]:
                Index_i = lista.index(i) 
                Index_i_ = Index_i - 1 
                while lista[Index_i] < lista[Index_i_]:
                    Valor = lista[Index_i]
                    lista[Index_i] = lista[Index_i_]
                    lista[Index_i_] = Valor

                    if Index_i_ != 0:
                        Index_i_ -= 1
                        Index_i -= 1

        return lista

#[4, 2, 1]
if __name__ == "__main__":
    
    os.system("cls")

    tamano_lista = int(input("驴De que tama帽o quieres la lista? "))

    lista = [random.randint(1, 100) for i in range(tamano_lista)]
    print(f"\nLista a ordenar: {lista}\n")

    Ordenamiento = Ordenamientos()

    print(f"Metodo Burbuja: {Ordenamiento.metodo_burbuja(lista)}\n")
    print(f"Metodo Inserci贸n: {Ordenamiento.metodo_insercion(lista)}\n")
import random 

#Imaginemos que lista es igual a [38, 35, 20]
def ordenamiento_por_insercion(lista):

    #Recorremos el indice desde 1 al final
    #Desde 1 porque se empieza desde el segundo elemento [38, ->35-<, 20]
    for indice in range(1, len(lista)):
        
        #Tomamos el valor actual = 35
        valor_actual = lista[indice]
        
        #Tomamos la posici贸n actual = 1
        posicion_actual = indice

        #Mientras que la posici贸n actual sea mayor al indice 0 (1 > 0 = TRUE) y nuestro elemento 
        #anterior sea mayor que nuestro n煤mero actual (38 > 35 = TRUE), quiere decir que a煤n debemos
        #Seguir moviendo nuestro valor a la izquierda
        while posicion_actual > 0 and lista[posicion_actual - 1] > valor_actual:
            #Aqui colocamos lista[1] = lista[0], es decir, asignamos 38 al indice del 35,
            #Nuestra lista en este punto quedaria [38, 38, 20]
            lista[posicion_actual] = lista[posicion_actual - 1]
            #Disminuimos en 1 la posici贸n inicial = 0
            #En este caso ya no seguir铆a el bucle 
            posicion_actual -= 1

        #Si llegamos aqui, significa que ya no hay elementos que verificar a nuestra izquierda
        #es decir, solo nos queda redefinir nuestro valor actual a el indice m谩s bajo que quedo
        #lista[0] = 35
        #[35, 38, 20]
        lista[posicion_actual] = valor_actual
    
    return lista
    #De esa forma trabajar铆a en cada ciclo, solo que en el segundo ciclo, el va a mover
    #el 38 al indice 2 [35, 38, 38] luego el 35 al indice 1 [35, 35, 38]
    #Y al final agregaria el valor 20 al indice 0 [20, 35, 38]

C贸digo

Consola

Una de las caracter铆sticas del ordenamiento por inserci贸n es que ordena en 鈥渟u lugar.鈥 Es decir, no requiere memoria adicional para realizar el ordenamiento ya que simplemente modifican los valores en memoria.

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.

S茅 que no es como el profesor lo pidio, pero as铆 fu茅 como logr茅 desarrollarlo es que es un poco ambiguo como lo explica.

import random

def ordenamiento_insercion(lista):

    n = len(lista)
    lista_desord = lista
            
    for i in range(1, n):
        valor_actual = lista_desord[i]
        indice = i - 1
        while indice >= 0:
            if valor_actual < lista_desord[indice]:
                aux = lista_desord[indice]
                lista_desord[indice] = valor_actual
                lista_desord[indice + 1] = aux
            indice -= 1
                                     
    return lista_desord
                
                    
if __name__ == "__main__":
    tamano_de_la_lista = int(input('De que tamano sera la lista? '))        
    lista = [random.randint(0, 100) for i in range(tamano_de_la_lista)]  
    print(lista)
    lista_ordenada = ordenamiento_insercion(lista)
    print(lista_ordenada)