Ordenamiento por inserció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

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

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

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

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

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.

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

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 😦

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

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)

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

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

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

https://upload.wikimedia.org/wikipedia/commons/0/0f/Insertion-sort-example-300px.gif
Este gif lo explica mejor.

Explicación del código del profesor

import random

def ordenamiento_por_insercion(lista):
    # Comienza un bucle que recorrerá la lista desde el segundo elemento (índice 1) hasta el último.
    for indice in range(1, len(lista)):
        # Obtiene el valor del elemento actual en la posición 'indice'.
        valor_actual = lista[indice]
        # Inicializa una variable 'posicion_actual' con el valor de 'indice'.
        posicion_actual = indice 
        # Comienza un bucle while que se ejecutará mientras 'posicion_actual' sea mayor que 0 y el elemento
        # anterior en la lista sea mayor que el 'valor_actual'.
        while posicion_actual > 0 and lista[posicion_actual - 1] > valor_actual:
            # Mueve el elemento anterior hacia la derecha en la lista, abriendo espacio para el 'valor_actual'.
            lista[posicion_actual] = lista[posicion_actual - 1]
            # Decrementa 'posicion_actual' para seguir comparando con elementos anteriores.
            posicion_actual -= 1

        # Cuando el bucle while termina, encontramos la posición correcta para el 'valor_actual'.
        # Asigna el 'valor_actual' en esa posición.
        lista[posicion_actual] = valor_actual

    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)]
    print("Lista Original: ", lista)

    lista_ordenada = ordenamiento_por_insercion(lista)
    print("Lista ordenada: ", lista_ordenada)

Yo use dos for

import random

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

        for a in range(i,-1,-1):
            if act < lista[a-1]:
                lista[a] = lista[a-1]
            else:
                break
        lista[a] = act

    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)

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)

cuando es lectura le impulsa a uno a hallar y entender el metodo por sus propios medios increible por que le enseña a uno mismo de no depender de alguien mas para encontrar conocimiento o entender problemas

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

Creo que lo implemente al revés

def ordenamiento_inserción(lista):
    
    Lista_Desordenada = lista
    Lista_Ordenada = []
    for i in Lista_Desordenada:
        if len(Lista_Ordenada) == 0:
            Lista_Ordenada.append(Lista_Desordenada[0])
        else:
            for j in range(0, len(Lista_Ordenada)):
                if i > Lista_Ordenada[j]  and Lista_Ordenada[j] == max(Lista_Ordenada):
                    Lista_Ordenada.append(i)
                elif i > Lista_Ordenada[j] :
                    pass
                elif i <= Lista_Ordenada[j]:
                    Lista_Ordenada.insert(j,i)
                    break
    return Lista_Ordenada

• Juzgue la lectura, pero si ya se ha visto esto en otros cursos realmente está bien explicada. Y creo que esta no es la favorita el profe 😅

• Y como es un for y un while seria en el peor de los casos O(n^2) y en el mejor de los casos O(n)

Se me figuro el bubble sort, pero este en lugar de 2 for anidados, tienes un while dentro del for, en el bubble recordemos que al ser O(n**2) te da una parabola, esta es una linea recta, la grafica sera lineal.

La gente quejandose por quejarse 🙄, a veces toca leer amigos

Resumen con ayuda visual

Vas comparando los elementos hasta que encuentren su lugar en la serie de 1 a 1. Por ejemplo, si queremos ordenar de menor a mayor, coge los valores de la izquierda y si es menor que todos lo enviaría de primera sino busca donde corresponde y si es mayor se compara con el que sigue enviándolo a su izquierda y asi va subiendo el mayor a la derecha y el menor a la izquierda.

• Es un algoritmo eficiente para serie de datos cortas, pero no para largas.

Les dejo el link de un video que me ayudo mucho a entender este concepto. Si no entendiste la clase , no te preocupes , revisa otras fuentes. Nunca se rindan.
https://www.google.com/url?sa=i&url=https%3A%2F%2Fwww.youtube.com%2Fwatch%3Fv%3DbB8Px8D9QdQ&psig=AOvVaw3j4OM4X_EjwidBbxx83Bkj&ust=1687229445378000&source=images&cd=vfe&ved=0CBAQjhxqFwoTCOjTw9Gpzv8CFQAAAAAdAAAAABAH

Les comparto mi implementación, un poco diferente:

def insercion(lista):
  lista_ordenada = [el for el in lista]
  for indice_actual in range(1, len(lista)):
    j = indice_actual - 1
    while j >= 0 and lista_ordenada[j] > lista_ordenada[j+1]:
      lista_ordenada[j], lista_ordenada[j+1] = lista_ordenada[j+1], lista_ordenada[j]
      j -= 1
  return lista_ordenada

Gracias al aporte de @Andres López “https://visualgo.net/es/sorting” se entiende mucho mejor.

hola, asi implementé el algoritmo;

def ordenamiento_por_insercion(lista:list):

    #
    lista_ordenada =[]
    #primer elemento se agrega a la ista ordenada
    lista_ordenada.append(lista[0])
  
    
    for i in range(1, len(lista)):

        valor_actual = lista[i]
        lista_ordenada.append(valor_actual)
        
        
        for j in range(len(lista_ordenada)-1,0,-1):

                        
            if lista_ordenada[j] < lista[j-1]:

                #mover a la derecha
                lista_ordenada[j] , lista_ordenada[j-1] = lista_ordenada[j-1] , lista_ordenada[j]

                
                
    return lista_ordenada

Les comporto el código entero de este algoritmo.

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_lista = int(input("De que tamaño será la lista: "))
    lista = [random.randint(0,100) for i in range(tamano_lista)]
    print(lista)

    lista_ordenada = ordenamiento_por_insercion(lista)
    print(lista_ordenada)

Esta fue mi implementación:

import random

def insertion(numbers):
	
	sorted_list = [numbers[0]]
	size = len(numbers) - 1
	for i in range(size):
		current_value = numbers[i + 1]

		j = len(sorted_list) - 1
		flag = False
		while j >= 0:
			if flag:
					sorted_list.pop(j+1)

			if current_value < sorted_list[j]:
				sorted_list.insert(j, current_value)
				flag = True
				j -= 1
			else:
				sorted_list.insert(j + 1, current_value)
				j = -1

	return sorted_list


if __name__ == '__main__':
	size_of_list = int(input('What is the size of numbers list? '))
	
	numbers = [random.randint(0, 100) for i in range(size_of_list)]
	print(numbers)

	sorted_numbers = insertion(numbers)
	print(sorted_numbers)

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__':
    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(f"Lista Desordenada = {lista}")

    lista_ordenada = ordenamiento_por_insercion(lista)
    print(f"Lista Ordenada = {lista_ordenada}") 

Acá está mi código con la solución:

Y acá está el output:

Les comparto mi implementación explicada en los comentarios del código:

def ordenamiento_insercion(lista):

    for i in range (1, len(lista)): 
        # Empezamos el recorrido en [1] porque el primer valor 
        # de la lista [0] se supone ordenado, y 
        # no se puede comparar con valores anteriores 

        for j in range (i,0,-1):    
            # Recorre la lista en forma descendente desde el valor actual [i]
            # para comparar este valor con los valores de los ínices 
            # anteriores hasta [0] 
            if lista [j] < lista[j -1]:
                # Para cada valor actual, si el valor actual
                # es menor que el valor del indice anterior 
                lista [j], lista[j -1] = lista [j-1], lista[j]  
                # entnces se intercambian las posiciones
                # lo cual es equivalente a mover el valor 
                # anterior a la derecha
    return lista

Comparto mi código de la clase añadiendo el paso a paso de como se van acomodando las numeros, hasta llegar a la lista final y ordenada

import random

def ordenamiento_por_insercion(lista):

    print(f"Imprime la lista original {lista}")
    vuelta = 0

    for indice in range(1, len(lista)):
        vuelta += 1
        print(f"Esta es la vuelta {vuelta}")
        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
        
        print(f"La lista va quedando asi {lista}")

        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(f"La lista se encuentra ordenada {lista_ordenada}")

import random 

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__':
    
    tamano_de_lista = int(input('De qué tamaño será la lista? '))
    
    lista = [random.randint(0, 100) for i in range (tamano_de_lista)]
    
    lista_ordenada = ordenamiento_insercion(lista)
    
    print(lista)
    print(lista_ordenada)

exactamente asi lo hacia en c++

for(int i=0;i<sizeof(list);i++){
	int pos=i;
	num=list[i];
	
	while((pos>0)&&list[pos-1]>num){
		list[pos]=list[pos-1];
		pos--;
	}
	list[pos]=num;
}```