Análisis De Algoritmos

Control Semana 7

Christopher Otazo

Análisis De Algoritmos

Instituto IACC

Octubre 2019

Desarrollo

1. Suponga que tiene que ordenar todas las facturas de un año por mes y día (desde el 1 al

1. de enero, lo mismo para marzo, abril, etc.).

1. ¿Qué algoritmo utilizaría: bubble sort o merge sort? ¿Por qué?
2. Enumere los pasos que haría para un mes.
3. ¿Qué diferencias tendría su solución respecto al algoritmo que no utilizó?

Respuesta

1. El primer paso es ordenar las facturas mes a mes y luego por año, para este tipo de

ordenamiento utilizaremos Merge Sort, ya que tenemos que considerar siempre el peor de los casos, y este sería que nuestros conjuntos (facturas) estén completamente desordenados, por lo que Bubble Sort tiene la desventaja de realizar demasiadas comparaciones, siendo a veces innecesarias. Vamos a ejemplificar el mes de enero en ambos casos, el elegido (Merge Sort) y el descartado (Bubble Sort) para hacer las comparaciones pertinentes y así fundamentar mi elección.

Suponiendo que cada día se realizó una factura, nuestro conjunto para el mes de enero tendría 31 elementos.

 [pic 1]

Como podemos apreciar tenemos una lista de 31 elementos totalmente desordenados, ahora Merge Sort dividirá este array en 2 partes iguales quedándonos algo asi:

[pic 2]

Merge Sort generara tantas divisiones hasta obtener conjuntos de 1 elemento.

[pic 3]

[pic 4]

[pic 5]

En este punto nuestro algoritmo comienza el proceso de unión (merge) con cada conjunto ordenado.

[pic 6]

[pic 7]

[pic 8]

[pic 9]

De esta manera nuestra lista queda ordenada de menor a mayor, el algoritmo de ordenamiento Merge Sort es utilizado en esta ocasión por ser más veloz y estable que Bubble Sort, a continuación observaremos como seria el ordenamiento con dicho algoritmo.

[pic 10]

Como podemos observar tenemos la misma lista desordenada del primer ejemplo, ahora procederemos a ejecutar el algoritmo.

[pic 11]

[pic 12]

[pic 13]

[pic 14]

[pic 15]

[pic 16]

[pic 17]

[pic 18]

[pic 19]

[pic 20]

[pic 21]

[pic 22]

[pic 23]

[pic 24]

[pic 25]

[pic 26]

[pic 27]

[pic 28]

[pic 29]

[pic 30]

[pic 31]

[pic 32]

[pic 33]

[pic 34]

[pic 35]

[pic 36]

. [pic 37]

[pic 38]

[pic 39]

[pic 40]

[pic 41]

[pic 42]

[pic 43]

[pic 44]

[pic 45]

[pic 46]

[pic 47]

[pic 48]

[pic 49]

[pic 50]

[pic 51]

[pic 52]

[pic 53]

[pic 54]

[pic 55]

[pic 56]

[pic 57]

[pic 58]

[pic 59]

[pic 60]

[pic 61]

[pic 62]

[pic 63]

[pic 64]

[pic 65]

[pic 66]

[pic 67]

[pic 68]

[pic 69]

[pic 70]

[pic 71]

[pic 72]

[pic 73]

[pic 74]

[pic 75]

[pic 76]

[pic 77]

[pic 78]

[pic 79]

[pic 80]

[pic 81]

[pic 82]

[pic 83]

[pic 84]

[pic 85]

[pic 86]

Desde esta perspectiva, continuar arreglando la lista sería demasiado tedioso, por lo que decidí dejar la explicación de lado, considerando la cantidad absurda de veces que el algoritmo recorre la lista ordenándola a priori se puede establecer, que si bien es cierto, Bubble Sort es el algoritmo más fácil de implementar, es completamente inútil ante listas grandes de elementos (considerando que 31 elementos no es una lista exageradamente grande) este algoritmo puede ser efectivo en listas extremadamente pequeñas o en arreglos ordenados casi en su totalidad. Es por este motivo que el algoritmo elegido para este planteamiento es Merge Sort.

...