Contenido principal
Ciencias de la computación
Curso: Ciencias de la computación > Unidad 1
Lección 5: Ordenamiento por inserciónAná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 . Así como cada llamada a
insert
en los elementos en los índices 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 elementos, todos los 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 . Por lo tanto, podrían ser necesarias hasta líneas para insertar en un subarreglo de elementos.
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 Supón que en cada llamada a . La segunda vez, . La tercera vez, . Y así sucesivamente hasta la última vez, cuando . Por lo tanto, el tiempo total que tarda la inserción en un subarreglo ordenado es
insert
, el valor que se está insertando es menor que cada elemento en el subarreglo a su izquierda. Cuando llamamos insert
la primera vez, Esa suma es una serie aritmética, excepto que va hasta en lugar de . 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
Al usar notación Θ grande, descartamos el término de orden inferior y los factores constantes y 1/2, para obtener el resultado de que el tiempo de ejecución de la inserción, en este caso, es de .
¿El ordenamiento por inserción puede tardar menos tiempo que ? 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 llamadas a , entonces el tiempo total para el ordenamiento por inserción es , que es , no .
insert
tarda solo un tiempo constante. Supón que cada llamada de insert
tarda un tiempo constante. Como hay insert
, si cada llamada tarda un tiempo que es alguna constante ¿Cualquiera de estas dos situaciones puede ocurrir? ¿Cada llamada a . ¿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.
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 ¿Qué hay del caso contrario? Una llamada a . 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.
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 ¿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 elementos recorrería hacia un lado a 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 , como en el peor de los casos.
insert
en un subarreglo de ¿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 elementos sería a lo más . Sobre todas las llamadas a , que es , como en el mejor caso. Entonces el ordenamiento por inserción es rápido cuando se le da un arreglo casi ordenado.
insert
recorre a lo más a 17 elementos, y el tiempo de una llamada de insert
en un subarreglo de insert
, el tiempo de ejecución sería Para resumir los tiempos de ejecución del ordenamiento por inserción:
- El peor caso:
. - El mejor caso:
. - El caso promedio para un arreglo aleatorio:
. - El caso "casi ordenado":
.
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 . No puedes decir que se ejecuta en un tiempo en todos los casos, ya que el mejor caso se ejecuta en un tiempo . Y no puedes decir que se ejecuta en un tiempo en todos los casos, ya que el tiempo de ejecución del peor caso es .
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.
¿Quieres unirte a la conversación?
- Me encuentro leyendo ese famoso libro, introducción a los Algoritmos, y la verdad este material es igual de bueno, sigue a el pie de la letra el ejemplo y lo da a entender.
De verdad este es uno de los sitios educativos mas efectivos que he visto hasta el momento, los felicito sigan así por favor.(9 votos) - se diria que la apliacacion y las regla de insercion tiene un tiempo de solucion teniendo en cuenta los procesos a seguir en la aplicacion(1 voto)
- que es Análisis del ordenamiento por inserción?(1 voto)
- 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(2 votos)