Presentación inserción directa y binaria

Métodos de ordenación

1. ●Durán Rodríguez Mayra
●Lopez Maldonado Victor
●Tona Castro Claudia
Universidad Autónoma de Baja California
Facultad de Ciencias Químicas e Ingeniería
Algoritmos y Estructuras de Datos
Métodos de Ordenación

2. Inserción Directa

3. Este algoritmo es una manera muy natural de
ordenar para un ser humano se basa en hacer
comparaciones. Son imprescindibles dos cosas:
❏Un arreglo o estructura similar de elementos
comparables.
❏Un criterio claro de comparación, tal que
dados dos elementos se diga si están en
orden o no.



Introducción

4. No se tiene un origen en específico o más bien no se
atribuye su descubrimiento a alguien, puesto que desde la
existencia de las computadoras casi cualquier persona
que pudiera tener alcance a ellas, pudo haber
implementado el método de inserción directa.

Antecedentes

5. Consiste en recorrer todo el arreglo comenzando desde el
segundo elemento hasta el final.

Se trata de colocar cada elemento en el lugar correcto,
entre todos los elementos anteriores a él o sea entre los
elementos a su izquierda en el arreglo.

Ordenamiento por Inserción Directa

6. ❏ Funcionamiento sencillo.
❏Estabilidad.
❏No intercambia registros con claves iguales.
❏ Una variable adicional para realizar los
intercambios.
Características

7. Algoritmo
1.Se asigna el primer valor del arreglo como
la parte ordenada, y se procede a
comparar el siguiente número.


2.Se toma el primer número de la parte
desordenada.
Al inicio, siempre es el segundo, que será
alojado en una variable temporal.




3.Se compara el número anterior con la
variable auxiliar.

8. Algoritmo
4.Si el número auxiliar es menor, se recorre
el arreglo y se inserta el número, en caso
de ser mayor, el arreglo permanece igual.




5.Seguimos por el tercer elemento.




6.Como el tercer elemento es mayor a los
anteriores, el arreglo permanece igual y se
continúa con el siguiente elemento.

9. Algoritmo
7.Debido a que el elemento actual es
menor, se compara con los anteriores, se
recorre el arreglo y se inserta el número
correspondiente.





8.El siguiente elemento es mayor a los
anteriores, por lo tanto el arreglo
permanece igual y se continúa con el
siguiente elemento.

10. Algoritmo
9.El último elemento es menor, por lo tanto
se compara con los anteriores, se recorre
el arreglo y se inserta el número.






El arreglo ordenado quedaría de la
siguiente manera:

11. ❏En el mejor de los casos, el arreglo estará inicialmente
ordenado.
F(n) = Ω(n)
❏En el peor de los casos, el arreglo estará inversamente
ordenado .
F(n) = O(n
2
)
❏En cualquier otro caso, cuanto más ordenada esté
inicialmente más se acerca a F(n)=O(n) y cuanto más
desordenada, más se acerca a F(n) = θ (n
2
) .


Tiempo de Ejecución

12. Inserción Binaria

13. La Inserción Binaria, es un tipo de
ordenamiento interno y a su vez una mejora de
la Inserción Directa.

Se diferencia simplemente en la búsqueda de
la posición de la Inserción.
Introducción

14. No cuenta con un autor reconocido, ni documentación
sobre su descubrimiento.

Sin embargo, el algoritmo cuenta con una licencia de
código abierto MIT/X11 y se puede deducir que el
algoritmo se originó en el Instituto de Tecnología de
Massachusetts (MIT).


Antecedentes

15. Consiste en tomar cada elemento del arreglo para ser
ordenado, y lo compara con los que se encuentran en
posiciones anteriores o posteriores a la del centro del
arreglo.

Este ordenamiento es recomendable sólo cuando n es
pequeña.


Ordenamiento por Inserción Binaria
2 3 5
4

16. ❏El número de intercambios puede reducirse en
aproximadamente un 25% para los datos aleatorios,
esto lo hace tener mejor rendimiento.

❏La secuencia destino donde debe insertarse el nuevo
elemento ya está ordenada.

❏Búsqueda Binaria para localizar el lugar de inserción.


Características

17. ❏Por ser de ordenación interna el acceso a cada
elemento es más rápido.

❏Ahorra memoria, ya que solo utiliza un arreglo y sobre él
se realiza la ordenación.

❏Menor número de comparaciones que el método de
inserción directa.
Características

18. Algoritmo

19. Algoritmo

20. Algoritmo

21. Algoritmo

22. ❏En el mejor de los casos, el arreglo estará inicialmente
ordenado.
F(n) = Ω(nLog
n
)
❏En el peor de los casos, el arreglo estará inversamente
ordenado .
F(n) = O(n
2
)
❏En cualquier otro caso, el número de comparaciones y
el número de asignaciones es de orden cuadrático.
F(n) = θ (n
2
)
Tiempo de Ejecución

23. ❏Compresión de datos.
❏Detectar duplicados.
❏Mostrar ficheros.
❏Ordenar resultados de una búsqueda.
❏Mostrar listado ordenado del contenido de una base de
datos.
❏Informática Gráfica.



Aplicaciones

24. ❏María Adriana Corona Nakamura, María de los Ángeles Ancona Valdez. (2011).
DISEÑO DE ALGORITMOS Y SU CODIFICACIÓN EN LENGUAJE C. México, D.F.: Mc
Graw Hill.

❏Luis Joyanes Aguilar, Luis Rodriguez Baena, Matilde Fernandez Azuela. (1996).
Fundamentos de Programación. España: Mc Graw Hill.

❏Luis Joyanes Aguilar, Luis Zahonero Martínez. (2005). Programación en C:
metodología, algoritmos y estructura de datos. España: McGraw Hill.


Referencias

25. ¡Gracias!