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 valor de Heap-size[A] será Heap-size[A]-1; con esto el elemento de mayor valor queda en la última posición como posteriormente se ejecuta MAX-HEAPIFY el ordenamiento que este realiza se aplicara solo para los Heapsize[A]-1 elementos, lo cual se segura que el elemento que al inicio de cada ciclo era el de mayor valor después de ser movido a la posición A[i] no será reordenado por el MAX-HEAPIFY. Esto es que al término de cada ciclo los n elementos que han comenzado en la posición A[1] están ordenados (siendo n el número de veces que se ha efectuado el ciclo).

Terminación: El ciclo for se ejecuta hasta que solo quedan 2 elementos en el arreglo, y al término de esta iteración todos los elementos del arreglo están ordenados, con lo cual comprobamos que el algoritmo es correcto.

...