Algoritmos. Practica 2, 2013-2014

15/10/2013

UAM

PRACTICA 2 - A. ALGORITMOS

Jose Alberto León Seijas y Carlos Mesón de Arana | eps
0

1

Índice
1

– MergeSort
1.1
1.2
1.3
1.4
1.5

– Ejercicio 1 (Pág 3 – 4)
– Ejercicio 2 (Pág 5)
– Ejercicio 3 (Pág 6 - 7)
– Ejercicio 4 (Pág 8)
– Ejercicio 5 (Pág 8 - 9)

2

– Cuestiones teóricas (Pág 10 - 15)

3

– Conclusiones Finales (Pág 16)

4

–Valgrind (Pág 16 - 17)

2

MergeSort
EJERCICIO 1
Implementad en ordenar.c el algoritmo de ordenación correspondiente al
método conocido como MergeSort. El prototipo de las funciones que se necesitan
serán int mergesort(int* tabla, int ip, int iu) y la función de combinación int
merge(int* tabla, int ip, int iu, int imedio). Las dos rutinas devuelven ERR en caso de
error y el número deoperaciones básicas si no ha habido error, tabla es la tabla a
ordenar, ip es el primer elemento de la tabla, iu es el último elemento de la tabla,
imedio es el índice del punto medio de la tabla.

3

El algoritmo de MergeSort es recurrente, de forma que el mismo se llamará
hasta que quede como una tabla de un único elemento. A si mismo, el objetivo de la
función mergesort() crearcontinuamente subdivisiones del array en dos mitades para
ir facilitando el trabajo, “divide y vencerás”. Una vez hechas estas subdivisiones, el
siguiente paso es unirlas entre si a la vez que las ordenas, que es posible hacerlo con la
función merge(), donde se creará un array auxiliar del tamaño necesario para guardar
el resultado ordenador de los dos arrays que se estén comparando.

4

EJERCICIO 2A continuación, modificando el programa ejercicio5.c para utilizar el
algoritmo MergeSort, obtener la tabla correspondiente a la variación del tiempo
promedio de ejecución en función del tamaño de la permutación. Representad dicha
tabla y compararla con el resultado teórico del algoritmo.

Para hacer el ejercicio dos, únicamente tuvimos que cambiar el puntero a
función a MergeSort() yanalizar los resultados obtenidos en el fichero ejercicio5.log
(analizado en la pregunta teórica 1).

5

EJERCICIO 3
Implementad quicksort, quicksort1, medio y partir.

Es importante destacar que para implementar quicksort(), definimos a su vez
un quicksort1() para que cumpliese las condiciones de argumentos necesarias para
utilizar el puntero a función, puesto que typedef int (*pfunc_ordena)(int*, int, int).
Por otra parte, como la función partir() no devuelve número de OB, sino la posición del
6

medio, añadimos la línea de código OB = iu – ip, puesto que es el número de veces que
se ejecutará siempre para una cadena. El resto solo consiste en llamar recursivamente
a la función para las dos subdivisiones de la cadena.

Para codificar este partir, una vez devuelto laposición del pivote (que será la
primera posición para la segunda entrega), guardamos en clave el valor del pivote y lo
colocamos al principio. Lo siguiente consistirá en ir comparando los siguientes
elementos de la cadena con la clave, e intercambiándolos según sea necesario.

7

EJERCICIO 4
Modificad el programa ejercicio5.c para obtener la tabla de tiempos de
ejecución del algoritmoQuickSort1 en función del tamaño de la permutación y
representad dicha tabla comparándola con los resultados teóricos.

Para hacer el ejercicio cuatro, únicamente tuvimos que cambiar el puntero a
función a Quicksort1() y analizar los resultados obtenidos en el fichero
correspondiente (analizado en la pregunta teórica 1).

EJERCICIO 5

Utilizad la rutina aleat num de la práctica anteriorcomo para implementar
una rutina de pivote int medio rand(int *tabla, int ip, int iu) que devuelve como
posición del pivote un valor aleatorio entre ip e iu. Implementad otra rutina int
medio stat(int *tabla, int ip, int iu) que compare los valores de 1las posiciones ip, iu e
(ip+ iu)/2 y devuelva la posición que contenga el valor intermedio entre las tres.

8

Para la implementación de...