Implementation (Part 2)
Lección 6 de 9 del curso Ordenamiento por inserción - Serie de DSA de Coddy.
Escenario: Ordenando [5, 2, 9, 1, 5]
Paso 1: Estado Inicial
- Arreglo Original: [5, 2, 9, 1, 5]
- Imagina esto como nuestra mano de cartas (o un arreglo de números).
Paso 2: Primer Elemento (i=1, key=2)
- Comenzamos con la segunda carta (elemento): key = 2.
- Compara 2 con 5 (el único elemento ordenado hasta ahora).
- Dado que 2 es menor, desplazamos el 5 a la derecha e insertamos el 2 en su lugar.
- Arreglo Actualizado: [2, 5, 9, 1, 5]
Paso 3: Segundo Elemento (i=2, key=9)
- Pasamos a la siguiente carta: key = 9.
- Compara 9 con 5.
- Dado que 9 es mayor, no es necesario desplazar.
- Arreglo Actualizado: [2, 5, 9, 1, 5] (sin cambios)
Paso 4: Tercer Elemento (i=3, key=1)
- Pasamos a la siguiente carta: key = 1.
- Compara 1 con 9, luego con 5.
- Desplaza 9 y 5 a la derecha, haciendo espacio para el 1.
- Arreglo Actualizado: [1, 2, 5, 9, 5]
Paso 5: Cuarto Elemento (i=4, key=5)
- Pasamos a la siguiente carta: key = 5.
- Compara 5 con 9.
- Dado que 5 es menor, no es necesario desplazar.
- Arreglo Actualizado: [1, 2, 5, 9, 5] (sin cambios)
Paso 6: Quinto Elemento (i=5, key=5)
- Pasamos a la última carta: key = 5.
- Compara 5 con 9.
- Dado que 5 es menor, no es necesario desplazar.
- Arreglo Actualizado: [1, 2, 5, 5, 9]
Resultado Final:
- Arreglo Ordenado: [1, 2, 5, 5, 9]
En cada paso, seleccionamos una carta (elemento), la comparamos con las que ya están ordenadas y la colocamos en el lugar correcto, desplazando las demás si es necesario. Repetimos este proceso hasta que todo el arreglo esté ordenado.
Desafío
FácilAhora, implementa el bucle interno, que realiza la ordenación para cada elemento.
Completa la ordenación dentro de la función insertionSort.
La función también debe imprimir los elementos del arreglo al final, uno por uno, con una nueva línea entre ellos.
Usa las lecciones anteriores y la pista como referencia :)
Pruébalo tú mismo
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
print(key)
Todas las lecciones de Ordenamiento por inserción - Serie de DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity