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

...