Ordenamiento por inserción
Ordenamiento por inserción es un experimento interactivo de Algoritmos en acción, una simulación gratuita de StudyFi Lab que funciona directamente en el navegador.
La ordenación por inserción funciona como ordenar cartas en la mano: la parte izquierda ya está ordenada y cada nuevo elemento (key) se desplaza a la izquierda hasta encontrar uno menor. Por el camino, los elementos mayores se mueven un lugar a la derecha. Con datos aleatorios es O(n²), pero con datos casi ordenados es casi O(n): un arreglo ordenado necesita solo n−1 comparaciones.
Prueba esto: Ejecútalo con un arreglo casi ordenado y luego con uno invertido. ¿Cuántas veces más desplazamientos necesita el invertido?
Preguntas frecuentes
¿Qué muestra el experimento «Ordenamiento por inserción»?
La ordenación por inserción funciona como ordenar cartas en la mano: la parte izquierda ya está ordenada y cada nuevo elemento (key) se desplaza a la izquierda hasta encontrar uno menor. Por el camino, los elementos mayores se mueven un lugar a la derecha. Con datos aleatorios es O(n²), pero con datos casi ordenados es casi O(n): un arreglo ordenado necesita solo n−1 comparaciones.
¿Cómo pruebo «Ordenamiento por inserción»?
Ejecútalo con un arreglo casi ordenado y luego con uno invertido. ¿Cuántas veces más desplazamientos necesita el invertido?
¿Estudias para un examen?
Sube tus apuntes y StudyFi los convierte en tarjetas, tests y pódcasts.