- Insertando
- Comparadas
- Intercambiadas
- Parte ordenada
Ordenamiento por inserción
El ordenamiento por inserción funciona como mucha gente ordena las cartas que tiene en la mano. Mantiene una parte ordenada al principio de la lista, toma el siguiente valor y lo desliza hacia atrás, más allá de cada valor mayor, hasta que encaja. Reproduce la ordenación a cualquier velocidad, o avanza de comparación en comparación, y observa los contadores de comparaciones, intercambios y pasadas. Pulsa Reproducir para ver la ordenación, o Paso y Atrás para avanzar de comparación en comparación. Arrastra el control de pasos para saltar a cualquier punto. Los recuadros cuentan comparaciones, intercambios y pasadas. Elige cuántas barras hay, cómo empiezan, o escribe tus propios números. Con el tablero seleccionado, las flechas avanzan paso a paso, la barra espaciadora reproduce y pausa, e Inicio y Fin saltan al principio y al final.
Cómo funciona
- Elige cuántas barras hay y cómo empiezan: aleatorias, casi ordenadas, invertidas o con pocos valores distintos. O escribe tus propios números.
- Pulsa Reproducir, o usa Paso y Atrás para avanzar de comparación en comparación. Arrastra el control de pasos para saltar a cualquier punto de la ordenación.
- Prueba una lista casi ordenada y otra invertida, y compara cuántas comparaciones necesita cada una.
Cómo funciona el ordenamiento por inserción
El primer valor por sí solo es una parte ordenada. Toma el segundo valor y compáralo con el anterior; si el anterior es mayor, intercámbialos, y sigue comparando e intercambiando hasta que el anterior no sea mayor o el valor llegue al principio. Ahora los dos primeros valores están en orden. Haz lo mismo con el tercer valor, el cuarto, y así hasta el final de la lista.
Rápido con listas casi ordenadas
Cada pasada se detiene en el primer valor que no es mayor, así que un valor que ya está cerca de su sitio solo cuesta una o dos comparaciones. Una lista ordenada necesita n − 1 comparaciones y ningún intercambio; una lista invertida, el peor caso, necesita n(n − 1)/2 de cada. El número de intercambios siempre es igual al número de inversiones de la lista inicial, los pares que están desordenados. Por eso el ordenamiento por inserción se usa a menudo para listas cortas o casi ordenadas, y dentro de ordenamientos más rápidos para terminar trozos pequeños.
Preguntas frecuentes
¿Cómo funciona el ordenamiento por inserción?
Construye una parte ordenada al principio de la lista. Cada pasada toma el siguiente valor y lo mueve hacia atrás, más allá de cada valor mayor que lo precede, hasta que encaja. Tras la pasada k, los primeros k + 1 valores están en orden, aunque un valor posterior aún puede insertarse entre ellos.
¿Cuántas comparaciones e intercambios hace el ordenamiento por inserción?
Los intercambios siempre igualan el número de inversiones de la lista inicial: ninguno para una lista ordenada, n(n − 1)/2 para una invertida. Las comparaciones son los intercambios más, como máximo, una por pasada, así que están entre n − 1 y n(n − 1)/2.
¿Por qué el ordenamiento por inserción es rápido con listas casi ordenadas?
Porque una pasada se detiene en cuanto encuentra un valor que no es mayor. Cuando cada valor está cerca de su lugar final, cada pasada es corta, y toda la ordenación tarda un tiempo cercano a n.
¿El ordenamiento por inserción es estable?
Sí. Un valor solo pasa por delante de valores estrictamente mayores, así que los valores iguales nunca se adelantan entre sí y conservan su orden original.
¿Se envían mis números a algún sitio?
No. La ordenación se ejecuta en tu navegador, y tus últimos ajustes se quedan en el almacenamiento local de este navegador.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Ir al editor