Control 7 analisis de algoritmos

Control Semana 7

xxxxxxxxxx

Análisis de Algoritmo

Instituto IACC

xxxx-xx-20xx

Desarrollo

1. Suponga que tiene que ordenar todas las facturas de un año por mes y día (desde el 1 al 31 de enero, lo mismo para marzo, abril, etc.).

a) ¿Qué algoritmo utilizaría: bubble sort o merge sort? ¿Por qué?

Para este caso el método a utilizar seria el de ordenamiento “Merge Sort”, ya que una de sus principales características es la eficiencia en el tiempo de ejecución. La forma de trabajar en pequeños conjuntos para ordenar los datos y luego unirlos. Tomando en cuenta los días del mes, se dividiría en dos, y empezar a ordenar en pequeños grupos para después de terminada la etapa de “Split”, se realiza el “Merge” poco a poco en los subconjuntos creados anteriormente utilizando la misma lógica de menos a más hasta obtener un total.

b) Enumere los pasos que haría para un mes.

1. Dividir en dos grupos la cantidad de días (depende del mes seleccionado)

2. Dividir en pares los dos grupos

3. Utilizar “Merge” en los grupos para comparar el número menor.

4. Estos se ordenan al comparar con el menor como en la etapa 1

5. se realiza cada paso en los grupos restantes para luego juntarse conservando el menor en la izquierda.

c) ¿Qué diferencias tendría su solución respecto al algoritmo que no utilizó?

La diferencia que se tiene al utilizar el método “Merge” y el método “Bubble”, es que dependiendo del mes va variando entre 30 y 31 números, entonces al utilizar “Bubble” sería mayor que el “Merge”, “Bubble” sería menos eficiente debido a las comparaciones que se tienen que realizar por mes.

2. Suponga el siguiente conjunto de elementos:

{1, 24, 56, 77, 2, 34, 54, 21, 90, 44, 8, 5, 7, 28, 31}

a) Ordénelos utilizando merge sort, quick sort y bubble sort y determine cuál algoritmo de ordenamiento es más eficiente.

SORT:

{1, 24, 56, 77, 2, 34, 54, 21, 90, 44, 8, 5, 7, 28, 31}

1, 24, 56, 77, 2, 34, 54 21, 90, 44, 8, 5, 7, 28, 31

1, 24, 56 77, 2, 34, 54 21, 90, 44, 8 5, 7, 28, 31

1 24 56 77 2 34 54 21 90 44 8 5 7 28 31

1, 24, 56 2, 34, 54, 77 8, 21, 44, 90 5, 7, 28, 31

1, 2, 24, 34, 54, 56, 77 5, 7, 8, 21, 28, 31, 44, 90

1, 2, 24, 34, 54, 56, 77, 5, 7, 8, 21, 28, 31, 44, 90

QUIK SORT:

1, 24, 56, 77, 2, 34, 54,21, 90, 44, 8, 5, 7, 28, 31

1, 7, 56, 77, 2, 34, 54, 21, 90, 44, 8, 5, 24, 28, 31

1, 7, 5, 77, 2, 34, 54,

...