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

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

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

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 “i”

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 “su 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)