Análisis del ordenamiento por inserción

Del mismo modo que el ordenamiento por selección, el ordenamiento por inserción itera sobre los índices del arreglo. Solo llama insert en los elementos en los índices $1, 2, 3, \ldots, n-1$1, comma, 2, comma, 3, comma, dots, comma, n, minus, 1. Así como cada llamada a indexOfMinimum tardó una cantidad de tiempo que dependía del tamaño del subarreglo ordenado, lo mismo pasa con cada llamada a insert. En realidad, la palabra "tarda" en el enunciado anterior debe ser "puede tardar" y vamos a a ver por qué.

Tomemos una situación en donde llamamos a insert y el valor que se inserta en un subarreglo es menor que cualquier elemento en el subarreglo. Por ejemplo, si estamos insertando 0 en el subarreglo [2, 3, 5, 7, 11], entonces todos los elementos del subarreglo tienen que recorrerse una posición hacia la derecha. Así que, en general, si estamos insertando en un subarreglo con $k$k elementos, todos los $k$k elementos podrían tener que recorrerse una posición. En lugar de contar exactamente cuántas líneas de código necesitamos para probar un elemento contra una llave y recorrer el elemento, convengamos que es un número constante de líneas; llamemos a esa constante $c$c. Por lo tanto, podrían ser necesarias hasta $c \cdot k$c, dot, k líneas para insertar en un subarreglo de $k$k elementos.

Supón que en cada llamada a insert, el valor que se está insertando es menor que cada elemento en el subarreglo a su izquierda. Cuando llamamos insert la primera vez, $k=1$k, equals, 1. La segunda vez, $k=2$k, equals, 2. La tercera vez, $k=3$k, equals, 3. Y así sucesivamente hasta la última vez, cuando $k = n-1$k, equals, n, minus, 1. Por lo tanto, el tiempo total que tarda la inserción en un subarreglo ordenado es

$c \cdot 1 + c \cdot 2 + c \cdot 3 + \cdots c \cdot (n-1) = c \cdot (1 + 2 + 3 + \cdots + (n-1))$c, dot, 1, plus, c, dot, 2, plus, c, dot, 3, plus, \@cdots, c, dot, left parenthesis, n, minus, 1, right parenthesis, equals, c, dot, left parenthesis, 1, plus, 2, plus, 3, plus, \@cdots, plus, left parenthesis, n, minus, 1, right parenthesis, right parenthesis .

Esa suma es una serie aritmética, excepto que va hasta $n-1$n, minus, 1 en lugar de $n$n. Al usar nuestra fórmula para una serie aritmética, obtenemos que el tiempo total que tarda la inserción en el subarreglo ordenado es

$c \cdot (n-1+1)((n-1)/2) = cn^2/2 - cn/2$c, dot, left parenthesis, n, minus, 1, plus, 1, right parenthesis, left parenthesis, left parenthesis, n, minus, 1, right parenthesis, slash, 2, right parenthesis, equals, c, n, squared, slash, 2, minus, c, n, slash, 2 .

Al usar notación Θ grande, descartamos el término de orden inferior $cn/2$c, n, slash, 2 y los factores constantes $c$c y 1/2, para obtener el resultado de que el tiempo de ejecución de la inserción, en este caso, es de $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis.

¿El ordenamiento por inserción puede tardar menos tiempo que $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis? La respuesta es sí. Supón que tenemos el arreglo [2, 3, 5, 7, 11], donde el subarreglo ordenado está formado por los cuatro primeros elementos, y estamos insertando el valor 11. Hasta la primera prueba, encontramos que 11 es mayor que 7, así que ningún elemento en el subarreglo necesita recorrerse hacia la derecha. Entonces esta llamada de insert tarda solo un tiempo constante. Supón que cada llamada de insert tarda un tiempo constante. Como hay $n-1$n, minus, 1 llamadas a insert, si cada llamada tarda un tiempo que es alguna constante $c$c, entonces el tiempo total para el ordenamiento por inserción es $c \cdot (n-1)$c, dot, left parenthesis, n, minus, 1, right parenthesis, que es $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, no $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis.

¿Cualquiera de estas dos situaciones puede ocurrir? ¿Cada llamada a insert puede causar que cada elemento en el subarreglo se recorra una posición a la derecha? ¿Cada llamada a insert puede causar que ningún elemento se recorra? La respuesta es sí a ambas preguntas. Una llamada a insert causa que cada elemento se recorra si la llave que está siendo insertada es menor que todos los elementos a su izquierda. Entonces, si cada elemento es menor que todos los elementos a su izquierda, el tiempo de ejecución del ordenamiento por inserción es $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis. ¿Qué significaría que cada elemento sea menor que el elemento a su izquierda? El arreglo tendría que empezar en orden inverso, como [11, 7, 5, 3, 2]. Entonces un arreglo ordenado de manera inversa es el peor de los casos para el ordenamiento por inserción.

¿Qué hay del caso contrario? Una llamada a insert no causa que ningún elemento se recorra hacia la derecha si la llave que está siendo insertada es mayor o igual que todos los elementos a su izquierda. Entonces, si todo elemento es mayor o igual a cualquier elemento a su izquierda, el tiempo de ejecución del ordenamiento por inserción es $\Theta(n)$\Theta, left parenthesis, n, right parenthesis. Esta situación ocurre si el arreglo inicia ya ordenado, y entonces un arreglo ya ordenado es el mejor caso para un ordenamiento por inserción.

¿Qué más podemos decir acerca del tiempo de ejecución del ordenamiento por inserción? Supón que el arreglo comienza ordenado de manera aleatoria. Entonces, en promedio, esperaríamos que cada elemento sea menor que la mitad de los elementos a su izquierda. En este caso, en promedio, una llamada a insert en un subarreglo de $k$k elementos recorrería hacia un lado a $k/2$k, slash, 2 de ellos. El tiempo de ejecución sería la mitad del tiempo del peor caso. Pero en notación asintótica, donde no importan los coeficientes constantes, el tiempo de ejecución en el caso promedio seguiría siendo $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis, como en el peor de los casos.

¿Qué pasa si supieras que el arreglo está "casi ordenado": cada elemento empieza a lo más a un número constante de posiciones, digamos 17, de donde se supone que debe estar cuando está ordendo? Entonces cada llamada a insert recorre a lo más a 17 elementos, y el tiempo de una llamada de insert en un subarreglo de $k$k elementos sería a lo más $17 \cdot c$17, dot, c. Sobre todas las $n-1$n, minus, 1 llamadas a insert, el tiempo de ejecución sería $17 \cdot c \cdot (n-1)$17, dot, c, dot, left parenthesis, n, minus, 1, right parenthesis, que es $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, como en el mejor caso. Entonces el ordenamiento por inserción es rápido cuando se le da un arreglo casi ordenado.

Para resumir los tiempos de ejecución del ordenamiento por inserción:

Si tuvieras que hacer una declaración general que aplique a todos los casos del ordenamiento por inserción, tendrías que decir que se ejecuta en un tiempo $O(n^2)$O, left parenthesis, n, squared, right parenthesis. No puedes decir que se ejecuta en un tiempo $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis en todos los casos, ya que el mejor caso se ejecuta en un tiempo $\Theta(n)$\Theta, left parenthesis, n, right parenthesis. Y no puedes decir que se ejecuta en un tiempo $\Theta(n)$\Theta, left parenthesis, n, right parenthesis en todos los casos, ya que el tiempo de ejecución del peor caso es $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.