Overview
La ordenación por inserción construye una porción ordenada insertando cada elemento nuevo en su posición correcta, como se ordenan cartas en la mano.
Analogy
Como ordenar cartas: tomas una carta nueva y la deslizas a la izquierda hasta que encuentre su lugar correcto.
Step-by-step
- Comienza con el segundo elemento (índice 1)
- Compáralo con los elementos anteriores y muévelos a la derecha si son mayores
- Inserta el elemento actual en la posición correcta
- Repite hasta que toda la lista esté ordenada
Visual
[5,3,1,4] → [3,5,1,4] → [1,3,5,4] → [1,3,4,5]
Common mistakes
- Olvidar guardar el elemento actual antes de mover elementos
- Condición de límite incorrecta en el bucle interno
Practice questions
- Ordena una lista pequeña a mano paso a paso
- Implementa e identifica cuándo la inserción supera a quicksort
Time
O(n²) peor caso, O(n) mejor caso (ya ordenado)
Space
O(1) — ordenación en sitio