Análisis de Algoritmos

Análisis de Algoritmos

Tarea 4.

1.- El código del MAX-HEAPIFY es muy eficiente en términos de los factores constantes, con la posible excepción de la llamada recursiva en la línea 10, que podría provocar a algunos compiladores generar código ineficiente. Escribe un MAX-HEAPIFY eficiente que utilice un constructor de control iterativo (un ciclo), en lugar de la recursividad.

MAX-HEAPIFY( A, i )

l←LEFT (i)

r←RIGTH (i)

While (( l≤ heap_size[A] and A[i]< A[l]) Or (r≤ heap_size[A] and A[i]< A[r]))

if( A[l] > A[r] )

temp ← A[i]

A[i] ← A[l]

A[l] ← temp

i ← l

else

temp ← A[i]

A[i] ← A[R]

A[r] ← temp

i ← r

l←LEFT (i)

r←RIGTH (i)

Para evitar los problemas que pueda causar el uso de la recursividad en el MAX-HEAPIFY se reescribió un código utilizando un ciclo while, con lo cual ya no es necesario el uso de la recursividad pues el ciclo permite llevar a cabo el ordenamiento de todos los elementos dentro del arreglo ya que después de ordenar un elemento el ciclo obliga a ordenar el siguiente hasta que ya no haya mas elementos que ordenar.

2.- Discutir la exactitud de de heapsort utilizando la siguiente invariante de lazo:

Al comienzo de cada iteración del ciclo for de las líneas de 2-5, el subarreglo A[1. . i] es un maxheap que contiene i elementos más pequeños de A [1. . n], y el subarreglo A[i + 1. . n] contiene los n - i elementos mayores de A [1. . n], ordenados.

Inicialización: Antes de la primera iteración del ciclo for (después de asignar a i el valor del tamaño total del arreglo y antes de revisar por primera vez si el tamaño de A es 2). Se tiene que el elemento de mayor valor dentro del arreglo se encuentra en la posición 1, además todos los padres tienen un valor superior al de cualquiera de sus hijos.

Mantenimiento: En cada iteración del ciclo while se cambia el elemento alojado en A[1] a la posición A[i] que es la última posición dentro del arreglo, después de esto indica que el nuevo

...