Ordenamiento por inserción
Construye una parte ordenada a la izquierda, un valor cada vez. Cada valor nuevo se saca y se mueve a la izquierda hasta llegar a un valor menor.
- Ω(n)
- Θ(n²)
- O(n²)
- O(1)
- sí
- sí
Mejor caso: cómo crece el tiempo con el tamaño n de la lista cuando la entrada es la más fácil para este algoritmo.
Caso medio: cómo suele crecer el tiempo con n. Con n², el doble de valores tarda unas cuatro veces más; n log n crece mucho más despacio.
Peor caso: el crecimiento con la entrada más difícil. Útil cuando la velocidad nunca debe caer.
Espacio: cuánta memoria extra hace falta además de la lista. 1 son unas pocas variables; n, una copia de la lista.
Estable: dos valores iguales conservan su orden original. Importa al ordenar registros por un solo campo.
Sin memoria extra: ordena dentro de la propia lista, sin una segunda lista.
- comparando
- moviendo
- en la mano
- parte ordenada
- en su lugar final
Prueba esto: Elige una lista casi ordenada. Casi nada se desplaza, así que termina en muy pocos pasos.
Cómo funciona
La parte izquierda siempre está ordenada. Se saca el siguiente valor, cada valor mayor de la parte ordenada se desplaza una posición a la derecha y el valor se coloca en el hueco. Así ordena mucha gente las cartas que tiene en la mano.
Cuándo es una buena opción
Buena opción para listas cortas y para listas casi ordenadas, donde es muy rápido. Las bibliotecas de ordenamiento reales lo usan para los trozos pequeños de la lista, dentro de métodos más rápidos.