FUNCION PARTICION

 

         La función partición utiliza los elementos definidos en el módulo TIPOS.O y recibe como entradas:

1.  - el vector en el que moverá el pivote, pasado por referencia, ya que se ha de modificar, no es conveniente duplicarlo, es decir, pasarlo por valor, ya que ocuparía con cada recursión más y más memoria.

2.  - los indices que indican la parte del vector que será modificada, es decir, elemento superior e inferior de la zona a modificar, con lo cual acotamos la zona del vector que se modificará.

3.  - el elemento que va a ser utilizado como pivote en la partición.

         La función emplea el algoritmo estudiado en las clases de teoría de la asignatura, es decir, dado un vector y un elemento (pivote), modifica la posición de dicho elemento hasta dejarla con todos lo elementos a su derecha mayores o iguales a él y con todos los elementos a su izquierda menores a él.

        

PROGRAMA QUICKSORT

 

         El programa QUICKSORT, que incluye el procedimiento del mismo nombre, muestra un menú donde se da a elegir la función que se quiere que realice el programa, es decir, si se quiere ordenar un vector, mediante el procedimiento quicksort, o si se quiere realizar el perfil temporal de dicha ordenación, tomando diversos tamaños de vector y obteniendo la media de varias pruebas para cada tamaño.

         Si se elige ordenar el vector, el programa pide la longitud que se le quiere dar y luego da a elegir entre introducirle el vector por teclado o que lo haga el programa por si solo, si se elige esta última opcion, el programa lo genera mediante el procedimiento genera_instancia, en caso contrario se pide al usuario que introduzca el valor de los elementos del vector a traves del teclado. Una vez dado el vector el programa lo ordena a traves del procedimiento quicksort.

         El procedimiento quicksort produce una partición del vector de entrada (o sea, de la zona del vector original sobre la cual actua ) y vuelve a actuar recursivamente sobre las dos partes generadas por el procedimiento partición.

 

 

 

 

 

PROCEDIMIENTO PERFIL

 

         La otra opción del programa, la de obtener el perfil temporal del programa de ordenación, es más automática ya que el programa a traves del módulo perfil.o genera los vectores con distintos tamaños, las distintas instancias y hace las repeticiones necesarias para obtener un resultado fiable, tomando como resultado final la media de los tiempos individuales.

         El resultado del procedimiento perfil se guarda en un vector que tiene la siguiente estructura:

 

tperfil_alg:

1	2	3	4	5	6	7	8	9	10	11	12	13
10	50	100	200	400	600	800	1000	1200	1400	1600	1800	2000
p  | m	p  | m	p  | m	p  | m	p  | m	p  | m	p  | m	p  | m	p  | m	p  | m	p  | m	p  | m	p  | m

 

         Se trata de un vector de registros, donde cada registro tiene tres campos, uno con el tamaño del vector para dicho caso, y otros dos donde guardará los resultados del perfil para los casos peor y el caso promedio de cada problema.

         El funcionamiento del procedimiento perfil es el siguiente:

         Para cada tamaño de problema el procedimiento perfil realiza diversas instancias, y para cada una de ellas, dependiendo del tamaño del vector, repite la ordenacion varias veces y obtiendo finalmente la media de las distintas repeticiones realizadas. Ademas tambien realiza el perfil en el caso peor de ordenación del vector, es decir, cuando el vector está ordenado de modo descendente.

         Los resultados obtenidos son los siguientes:

 

 

 

 

 

 

 

 

 

	Promedio	Peor
10	0.04	0.05
50	0.37	0.27
100	1.14	1.09
200	3.82	3.64
400	12.41	13.10
600	22.77	29.58
800	33.76	51.57
1000	44.77	78.26
1200	55.33	111.48
1400	66.25	150.80
1600	76.53	197.17
1800	86.20	247.52
2000	98.17	305.76

	Promedio	Peor
10	0.03	0.04
50	0.29	0.27
100	0.61	0.55
200	0.63	0.73
400	0.44	1.46
600	0.38	1.14
800	0.30	1.52
1000	0.49	1.82
1200	0.30	2.28
1400	0.52	0.000
1600	0.20	3.03
1800	0.24	0.000
2000	0.49	0.000