Ordenamiento por inserción

El ordenamiento por inserción es como la mayoría de la gente ordena una mano de cartas: toma la siguiente carta y la desliza a su sitio entre las que ya están en orden. Es lento con listas largas y aleatorias, pero muy rápido con listas cortas o casi ordenadas, y por eso las bibliotecas de ordenamiento reales todavía lo usan.

Barras ordenándose: una parte ordenada a la izquierda y una barra que retrocede hacia ella, más allá de las barras mayores
Barras ordenándose: una parte ordenada a la izquierda y una barra que retrocede hacia ella, más allá de las barras mayores

La idea

Mantén ordenado el principio de la lista. Al empezar, esa parte ordenada es solo el primer valor. Toma el siguiente valor y compáralo con el anterior. Si el anterior es mayor, intercámbialos y vuelve a comparar, un lugar más atrás. Para cuando el anterior no sea mayor o cuando el valor llegue al principio. La parte ordenada ha crecido en uno. Repite con cada valor hasta el final.

Un ejemplo

Toma 5, 1, 4, 2, 8. La pasada 1 toma el 1: 5 es mayor, así que se intercambian, y el 1 llega al principio: 1, 5, 4, 2, 8. La pasada 2 toma el 4: se intercambia con el 5 y se detiene en el 1: 1, 4, 5, 2, 8. La pasada 3 toma el 2: se intercambia con el 5 y con el 4, y se detiene en el 1: 1, 2, 4, 5, 8. La pasada 4 toma el 8, que ya es mayor que 5, así que basta una comparación. En total, 7 comparaciones y 4 intercambios. El ordenamiento de burbuja necesita 9 comparaciones con la misma lista, y el ordenamiento por selección, 10.

Los intercambios igualan las inversiones

Una inversión es un par de valores en el orden equivocado. Intercambiar dos vecinos desordenados elimina exactamente una inversión, y el ordenamiento por inserción solo intercambia vecinos así. Por tanto, hace exactamente tantos intercambios como inversiones tiene la lista inicial, los mismos que el ordenamiento de burbuja. Además, cada pasada hace como máximo una comparación que no lleva a un intercambio: la que la detiene. Así que las comparaciones son las inversiones más, como máximo, n − 1.

Adaptativo: rápido cuando la lista está casi ordenada

Como el trabajo equivale al número de inversiones más aproximadamente n, el ordenamiento por inserción es rápido siempre que haya pocas inversiones. Una lista ordenada necesita n − 1 comparaciones y ningún intercambio. Una lista en la que cada valor está a pocos lugares de su sitio tarda un tiempo cercano a n. Solo una lista muy lejos de estar ordenada, como una invertida con n(n − 1)/2 inversiones, tarda un tiempo proporcional a n². En una lista aleatoria, la media es de unos n²/4 intercambios.

Dónde se usa

El ordenamiento por inserción es estable, no necesita memoria extra y tiene muy poca sobrecarga. Con listas cortas supera a algoritmos que son más rápidos sobre el papel. Muchos ordenamientos de bibliotecas, como Timsort en Python y Java y el introsort de C++, pasan al ordenamiento por inserción para los trozos pequeños de la lista, normalmente de hasta unas pocas decenas de valores. También sirve para datos que llegan de uno en uno, porque cada valor nuevo se puede insertar en cuanto llega.

Pruébalo

Abre la aplicación y pulsa Reproducir, o pulsa Paso para avanzar de comparación en comparación. El valor que se está insertando tiene su propio color, el valor con el que se compara está resaltado, y la parte ordenada es verde. A diferencia del ordenamiento de burbuja y del ordenamiento por selección, la parte verde no es definitiva: un valor menor que llegue después aún puede colarse en ella. Prueba una lista casi ordenada para ver lo cortas que son las pasadas, y luego una invertida.

Preguntas frecuentes

¿Cuál es la complejidad temporal del ordenamiento por inserción?

O(n²) en el peor caso y en el caso medio, y O(n) en el mejor caso, una lista ya ordenada. Más exactamente, tarda un tiempo proporcional a n más el número de inversiones. Solo necesita O(1) de memoria extra.

¿Qué diferencia hay entre el ordenamiento por inserción y el ordenamiento por selección?

El ordenamiento por selección recorre toda la parte desordenada para encontrar el menor valor, así que siempre hace n(n − 1)/2 comparaciones, pero pocos intercambios. El ordenamiento por inserción toma el siguiente valor tal como llega y solo lo mueve hacia atrás lo necesario, así que hace menos comparaciones, sobre todo con listas casi ordenadas, pero más intercambios.

¿Qué es el ordenamiento por inserción binaria?

Una variante que encuentra dónde va el nuevo valor con una búsqueda binaria en la parte ordenada, lo que requiere unas log n comparaciones en lugar de hasta n. Aun así, hay que desplazar los valores para hacer sitio, así que el número de movimientos, y el peor caso O(n²), no cambian.

¿El ordenamiento por inserción es estable?

Sí. Un valor solo retrocede más allá de valores estrictamente mayores, así que los valores iguales conservan su orden original.

¿Listo para probarlo?

Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.

Probar el ordenamiento por inserción