Scribd
Cargar
281 vistas13 páginas

Insertion Sort: Análisis y Ejemplo

Este documento presenta el algoritmo de ordenamiento por inserción. Explica que es un algoritmo simple que recorre una lista o arreglo seleccionando un valor como clave en cada iteración y comparándolo con los valores anteriores para insertarlo en la posición correcta. Analiza su complejidad temporal de O(n2) en el peor caso y de O(n) en el mejor caso. Finalmente, muestra un ejemplo del proceso de ordenamiento con números y el código correspondiente en C.

Cargado por

Gambrinus230278
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd
281 vistas13 páginas

Insertion Sort: Análisis y Ejemplo

Este documento presenta el algoritmo de ordenamiento por inserción. Explica que es un algoritmo simple que recorre una lista o arreglo seleccionando un valor como clave en cada iteración y comparándolo con los valores anteriores para insertarlo en la posición correcta. Analiza su complejidad temporal de O(n2) en el peor caso y de O(n) en el mejor caso. Finalmente, muestra un ejemplo del proceso de ordenamiento con números y el código correspondiente en C.

Cargado por

Gambrinus230278
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPTX, PDF, TXT o lee en línea desde Scribd

FACULTAD DE INGENIERÍA

WA CARRERA DE INGENIERIA DE SISTEMAS COMPUTACIONALES

Ordenamiento por Inserción


(Insertion Sort)
Integrantes:
• Marcelo Odar, Victor
• Yataco Rodríguez, Jonathan Eduard
• Valdivia Barandiarán, José Alberto

Docente:
• Tello Guzmán, José Luis

Curso:
• Análisis de Algoritmos y Estrategias de Programación
CONCEPTO
El logaritmo de ordenamiento por inserción es un logaritmo de fácil aplicación que
consiste en el recorrido por la lista o arreglo seleccionando en cada iteración un valor
como clave y compararlo con el resto, insertando este en el lugar correspondiente.

En la computación, el ordenamiento de datos cumple un rol muy importante, ya sea


como un fin en sí o como parte de otros procedimientos más complejos. Se han
desarrollado muchas técnicas en este ámbito, cada una con características
específicas, con ventajas y desventajas sobre las demás.

Este logaritmo es lento, pero puede ser de utilidad para las listas o arreglos que estén
ordenadas o semiordenadas, puesto a que en dichos casos realizará muy pocos
desplazamientos.
ANÁLISIS DEL ALGORITMO
En cuanto a tema de Estabilidad podemos decir que este logaritmo al no realizar
nunca intercambio de registros con claves iguales es “estable”.

Para el tiempo de ejecución de una lista de n elementos el ciclo externo se ejecuta


n-1 veces. El ciclo interno se ejecuta como máximo una vez en la primera iteración, 2
veces en la segunda, 3 veces en la tercera y así sucesivamente. Con lo cual podemos
determinar una complejidad de O(n 2).

Esto lo representaremos en las siguientes gráficas de rendimiento del algortimo:


RENDIMIENTO DEL ALGORITMO (WORST CASE)
En el peor de los casos, con los datos ordenados a la inversa, se necesita realizar 
(n-1) + (n-2) + (n-3) .. + 1 comparaciones e intercambios, o (n2-n)/2. Por lo tanto
la complejidad es en O(n2).
RENDIMIENTO DEL ALGORITMO (AVERAGE CASE)
En el caso medio, la complejidad de este algoritmo es también en O(n2)
RENDIMIENTO DEL ALGORITMO (BEST CASE)
En el caso óptimo y con los datos ya ordenados, el algoritmo sólo efectuará n
comparaciones. Por lo tanto la complejidad en el caso óptimo es en O(n).
PROGRAMACIÓN DEL CÓDIGO
• Para el siguiente ejemplo de ordenación, realizaremos el código en lenguaje C, la
cual fue probada en una máquina para la verificación del funcionamiento del caso
presentado.
EJEMPLO
Comenzamos con una lista de datos no ordenados.

Se selecciona el segundo valor como clave y se compara con los valores ubicados a
su izquierda y se inserta en el lugar correspondiente.
EJEMPLO
Se selecciona el siguiente número como clave y se repite el proceso para todos los
valores anteriores.
EJEMPLO
Se selecciona la siguiente clave.
EJEMPLO
Finalmente se selecciona la última clave.
EJEMPLO
Al finalizar el algoritmo tenemos como resultado la lista ordenada.
EJEMPLO
Tomamos de este ejemplo el código presentado en lenguaje C.

También podría gustarte