A partir de esta situacin, podemos disear un mtodo divide y vencers para
ordenar el vector: despus de hacer la particin, slo queda ordenar los dos subvectores. Lo haremos llamando recursivamente al mismo algoritmo de ordenacin, hasta
Algoritmos y Estructuras de Datos 3
que lleguemos al caso base en el cual el subvector tiene como mucho un elemento.
Una primera aproximacin al algoritmo propuesto sera la siguiente:
Prctica 2: Estudio del algoritmo Quicksort
algoritmo QUICKSORT(v:vector; ini,fin: entero)
var pos_pivote: entero;
Escuela Universitaria y Facultad de Informtica
si ini<fin entonces
hacer la particin de v[ini..fin];
{ (para todo k:ini<=k<pos_pivote:v[k]<=v[pos_pivote]) y
(para todo k:pos_pivote<k<=fin:v[k]>=v[pos_pivote]) y
ini<=pos_pivote<=fin }
Departamento de Sistemas Informticos y Computacin
Universidad Politcnica de Valencia
Curso 2000/01
QUICKSORT(v,ini,pos_pivote-1);
{ v[izq..pos_pivote-1] est ordenado }
QUICKSORT(v,pos_pivote+1,fin)
{ v[pos_pivote+1..fin] est ordenado }
1 Introduccin
El objetivo de esta prctica es el estudio terico y experimental del algoritmo rpido
de ordenacin conocido como Quicksort. Este algoritmo fue propuesto por Hoare en
1962 [Hoare, 62], y es uno de los ms e cientes algoritmos de ordenacin conocidos.
El problema de la ordenacin se puede enunciar de la manera siguiente: dado un
vector
v[1..N ]
de
tipobase,
establecer una permutacin de sus elementos de forma
fsi
fQUICKSORT
Sobre la correccin de este algoritmo hemos de sealar:
i : 1 i < N : v[i] v[i + 1],
en donde los elementos de
tipobase
En el caso general, es posible demostrar por induccin que el vector queda
ordenado, suponiendo que el algoritmo de particin se ajuste a su especi cacin.
Hay que hacer notar que en este caso, se hacen llamadas recursivas sobre los
admiten un orden total.
subvectores
Vamos a plantear la solucin de este problema de forma recursiva, suponiendo que
estamos interesados en resolver la ordenacin del subvector
En el caso base, cuando el vector est vaco o tiene un elemento, ste est
trivialmente ordenado.
que queden ordenados de forma creciente (o decreciente); es decir, que se cumpla:
v[ini..f in], 1 ini, f in
v[ini..pos_pivote 1]
N.
Supongamos que somos capaces de establecer una particin de este subvector de
siendo
manera que:
v[pos_pivote + 1..f in],
lo que asegura que son de menor talla que el
vector de partida.
1. Dado un elemento
cin,
ini pos_pivote f in,
escogido de entre los de
v[ini..f in],
tras ejecutar la parti-
ocupa el lugar que le corresponde en el vector ordenado.
2. Todos los elementos a la izquierda de
son menores o iguales que
los de la derecha son mayores o iguales que el mismo.
v
Al elemento
fin
elementos<=p
se le llama
pivote o
elementos>=p
clave de la particin.
y todos
2 Algoritmo de particin
En este apartado presentamos un algoritmo para la particin en que se basa el
algoritmo Quicksort. A continuacin describimos la estrategia a seguir:
Gr camente:
ini
p,
Elegimos como pivote
un elemento de
v[ini..f in].
menores o iguales que
mayores que
Por ejemplo, se puede
v[ini].
Se hace un recorrido del vector a partir de
dos variables
tomar el primer elemento
ini + 1,
situando los elementos
en una zona a la izquierda del vector, y los elementos
p en una zona a la derecha.
izq y der , de forma que:
Para realizar este recorrido, usaremos
izq
der
ini
v
fin
elementos<=p
elementos>p
Al nal del recorrido, llegaremos al siguiente estado
QUICKSORT(v,ini,der-1);
{ v[izq..der-1] est ordenado }
QUICKSORT(v,der+1,fin)
{ v[der+1..fin] est ordenado }
fsi
fQUICKSORT
der izq
ini
v
fin
elementos<=p
4 Anlisis de la complejidad temporal de Quicksort
elementos>p
A diferencia del algoritmo de ordenacin por fusin, Quicksort puede presentar diversas instancias, debidas al comportamiento de la particin. Se puede dar que la
por lo que acabaremos la particin intercambiando
v[ini]
v[der].
aplicacin de la particin por parte de sucesivas llamadas recursivas de Quicksort,
tenga comportamientos incluso opuestos sobre el mismo vector de entrada (consultar
p:=v[ini]; izq:=ini+1; der:=fin;
mientras izq<=der hacer
si v[izq]<=p entonces
izq:=izq+1
sino
intercambiar v[izq] y v[der];
der:=der-1
fsi
fmientras;
intercambiar v[ini] y v[der]
Con este recorrido se resuelve el problema con un coste
las cuestiones 5 y 8 de este boletn).
En general, podemos expresar la complejidad temporal de Quicksort a travs de
las siguientes relaciones de recurrencia:
coste(n) =
donde
coste(n ) + coste(n ) + kn,
k ,
n y n son las tallas de los subvectores
kn es debido al coste de la particin.
si
n > 1, n + n = n 1;
n 1,
a los que da lugar la particin.
El
trmino
Esta recurrencia presenta dos casos extremos, segn como sea el resultado de la
particin del vector:
(n).
3 El algoritmo Quicksort
Cada vez que se realiza la particin, se obtiene un vector vaco y otro de talla
n 1,
de forma que
n = n 1
la recurrencia tiene la forma:
Si usamos para la particin el algoritmo propuesto en el apartado anterior, el algo-
coste(n) =
ritmo de ordenacin Quicksort queda como sigue:
algoritmo QUICKSORT(v: vector; ini,fin: entero)
var izq, der: entero; p: tipobase;
si ini<fin entonces
p:=v[ini]; izq:=ini+1; der:=fin;
mientras izq<=der hacer
si v[izq]<=p entonces
izq:=izq+1
sino
intercambiar v[izq] y v[der];
der:=der-1
fsi
fmientras;
intercambiar v[ini] y v[der];
{ (para todo k:ini<=k<der:v[k]<=p) y p=v[der] y
(para todo k:der<k<=fin:v[k]>p) }
3
si
y, por tanto, resulta
n = 0,
para cualquier
coste(n 1) + kn,
k ,
si
si
n > 1.
En este caso,
n > 1;
n1
(n2 ).
Cada vez que se realiza la particin, se obtiene dos vectores aproximadamente
de la misma talla,
n n n/2. En este caso, la
2coste(n/2) + kn,
coste(n) =
k ,
recurrencia es de la forma:
Si, por simpli car, resolvemos esta recurrencia para
si
si
n > 1;
n 1.
n potencia de 2, se obtiene
coste(n) = nk + kn log2 n,
y, por tanto, resulta
(n log n).
Vamos a estudiar la complejidad del algoritmo en el caso medio. Veremos que
asintticamente se comporta como en el mejor de los casos.
elemento
Supongamos que el
seleccionado para hacer la particin es tal que le corresponde la
i-sima
i 1, y otro
(i = 1, 2, . . . , n)
posicin en el orden. De esta forma, se genera un subproblema de talla
de talla
n i.
Si adems consideramos que todas las posibilidades
equilibrada evitando en lo posible la contribucin de casos desequilibrados al coste
promedio.
Vamos a estudiar a continuacin un algoritmo de particin debido a Weiss [Weiss,95],
son igualmente probables, tenemos:
costem (n) =
que incide en los dos aspectos indicados para obtener un algoritmo de ordenacin
n
1
(kn + costem (i 1) + costem (n i))
n
i=1
mejor.
Las dos diferencias ms signi cativas entre el algoritmo de Weiss y el algoritmo
1
2costem (i 1)
= kn +
n
ya visto son, en primer lugar, la estrategia utilizada para seleccionar el pivote y, en
segundo lugar, el criterio de intercambio de elementos del vector que permite reducir
i=1
para
n > 1.
los efectuados durante la ejecucin del algoritmo.
Por tanto,
5.1 Eleccin del pivote
n1
kn + 2/n coste (i),
m
costem (n) =
i=0
k ,
si
n > 1,
si
n 1.
Naturalmente hay unas elecciones del pivote mejores que otras. Del estudio de costes
del algoritmo Quicksort parece razonable deducir que, cuanto ms equilibrada sea la
subdivisin realizada por particin ms prximo ser el comportamiento temporal
de Quicksort al de su caso mejor, esto es, en las expresiones del coste ms prxima
Por induccin se puede demostrar que:
ser la constante
n 2 : costem (n) k n ln n,
con
k = 2(k + k).
n1
i ln i
i=2
a su cota inferior
k.
como pivote, ya que todos ellos tienen la misma probabilidad de quedar centrados
Para ello, se puede usar la siguiente acotacin:
kr
Cuando la entrada al algoritmo es aleatoria cualquier elemento del vector servira
x ln xdx <
i=2
en la particin o en un extremo de ella; en ese caso la eleccin del primer elemento
es aceptable. Pero si el vector ya est parcialmente ordenado lo que es frecuente en
n2
n2
ln n .
2
4
la prctica entonces la eleccin del primer elemento har ms probables particiones
desequilibradas.
Una estrategia mejor consistira en usar como pivote un elemento cualquiera
Del anlisis anterior podemos sacar las siguientes conclusiones:
1. Las cotas de complejidad de Quicksort son
O(n2 )
del vector elegido al azar, evitando as elecciones de cientes debido a entradas no
aleatorias. El problema de esta ltima eleccin es que la generacin de un nmero
(n log n).
aleatorio puede ser temporalmente costosa, con lo que se penalizara el algoritmo de
2. Si la particin se comporta de manera que en promedio el pivote queda cen-
particin.
instancias que hemos considerado son efectivamente igualmente
Otra estrategia posible consiste en elegir el elemento central del vector en lugar del
probables en todos los niveles de la recursin), entonces el comportamiento
primero, de modo que particin dar, por lo general, subdivisiones ms equilibradas
trado (las
promedio de Quicksort ser
(n log n).
cuando la entrada ya est parcialmente ordenada, manteniendo la aleatoriedad de la
eleccin para entradas tambin aleatorias.
3. An en el supuesto del punto anterior, al promediar la contribucin al coste de
todas las instancias consideradas, aparece un trmino
2(k
+ k) ln 2,
frente al trmino
kn log2 n
kr n log2 n,
con
k < kr
del caso mejor.
En el siguiente apartado, mostraremos cmo se pueden tener en cuenta estos
resultados para buscar mejores implementaciones del algoritmo.
5 Otro algoritmo de particin
Si consideramos el algoritmo estudiado en la seccin 3, y suponemos como entrada
un vector completamente aleatorio, entonces el coste esperado por trmino medio es
kr n log2 n,
puesto que la particin elige un valor aleatorio al tomar como pivote el
primer elemento del vector.
Pueden conseguirse mejoras en el tiempo de ejecucin del algoritmo Quicksort
que se ha estudiado reduciendo
tratando de acercar
kr
la constante asociada a particin, y tambin
modi cando para ello la seleccin del pivote, de forma
La eleccin ptima del pivote consistira en seleccionar la mediana del vector,
esto es: aquel elemento que tiene un nmero igual de elementos mayores y menores
que el mismo. Esta eleccin garantizara siempre la subdivisin ms equilibrada; sin
embargo determinar la mediana de un vector tiene como mnimo un coste lineal, lo
que supone en la prctica una penalizacin temporal excesiva.
Otra estrategia distinta, la considerada por Weiss, consiste en seleccionar tres
elementos del vector:
el primero, el central y el ltimo, eligiendo como pivote la
mediana de los tres, esto es, el elemento intermedio. Este mtodo es, frecuentemente,
mejor que una eleccin puramente aleatoria (ver cuestin 11), ya que escoge como
pivote un elemento que estar con ms probabilidad cerca de la mediana que de
haberse elegido al azar; adems el mtodo elimina el caso malo que se produce
ante una entrada ordenada.
El algoritmo que mostramos a continuacin, debido a Weiss, determina el pivote
que utilizar el algoritmo de particin, para el subvector de
y
f in.
que la subdivisin en dos subvectores efectuada por el algoritmo de particin sea ms
comprendido entre
ini
{ fin - ini + 1 >= 3 }
algoritmo mediana3(v:vector; ini,fin:entero) devuelve tipobase
{ Determina la mediana de los elementos inicial, central y final,
ordena dichos elementos, y devuelve el pivote }
var centro: entero; pivote: tipobase fvar;
centro:=(ini+fin) div 2;
si v[ini]>v[centro] entonces intercambiar v[ini] y v[centro] fsi;
si v[ini]>v[fin] entonces intercambiar v[ini] y v[fin] fsi;
si v[centro]>v[fin] entonces intercambiar v[centro] y v[fin] fsi;
{ v[ini]<=v[centro]<=v[fin] }
pivote:=v[centro];
intercambiar v[centro] y v[fin-1]; {oculta el pivote}
devuelve pivote
fmediana3
(1) pivote := mediana3(v,ini,fin);
(2) izq:=ini; der:=fin-1;
repetir
(3)
repetir izq:=izq+1 hasta v[izq]>=pivote;
(4)
repetir der:=der-1 hasta v[der]<=pivote;
(5)
intercambiar v[izq] y v[der]
(6) hasta der <= izq;
(7) intercambiar v[izq] y v[der] {deshace el ltimo intercambio}
(8) intercambiar v[izq] y v[fin-1] {restaura el pivote}
{ v[izq]=pivote }
fparticin
De este algoritmo cabe resaltar lo siguiente:
1. El algoritmo
Como hemos indicado, adems de determinar el pivote, el algoritmo intercambia
entre s los elementos inicial, central y nal del subvector de forma que estn ordena-
mediana3
introduce en
ini
un elemento inferior o igual al pivote,
evitando tener que usar un centinela, o una condicin adicional, en la segunda
iteracin (lnea 4), para que la variable
der
no se salga de rango.
dos entre s lo que, adems de situar ya dichos elementos, garantiza la existencia de
un elemento inferior o igual al pivote en el extremo izquierdo, de forma que pueda
2. El intercambio que se produce en la lnea 5 tiene slo sentido cuando el valor
de
utilizarse como centinela en bsquedas posteriores.
izq
der . Esto ocurre en todas las iteraciones excepto en
izq der , como el intercambio tambin se realiza en la
es menor que el de
la ltima, en la que
5.2 Minimizacin de los intercambios efectuados
ltima iteracin es necesario deshacerlo al nalizar el bucle. La nalidad del
Del examen de la particin propuesta inicialmente (seccin 2) se puede comprobar
intercambio que no tena que haberse producido.
intercambio existente en la lnea 7 es, precisamente, la de deshacer el ltimo
que es posible intercambiar un elemento mayor que el pivote con otro que tambin lo
sea (ver cuestin 4). Este intercambio es claramente ine ciente y un mtodo mejor
consiste en intercambiar solamente un elemento mayor o igual que el pivote con otro
Naturalmente puede realizarse lo mismo si se elimina la lnea 7, y se sustituye la
lnea 5 por la siguiente:
si izq<der entonces intercambiar v[izq] y v[der]
que sea menor o igual (ver cuestin 7).
La estrategia seguida por Weiss consiste en que, en cada iteracin, se avanza
tanto como se puede en el recorrido por la izquierda y por la derecha del vector,
izq
der
ini
v
fin
<=p elementos<=p >=p
<=p elementos>=p
Pero de hacerse as, se efectuara una comparacin adicional en cada iteracin,
incrementando el tiempo de ejecucin del algoritmo.
hasta encontrar dos elementos posiblemente descolocados,
>=p
6 Actividades en el laboratorio
El trabajo en el laboratorio consistir en la implementacin del algoritmo Quicksort,
el estudio experimental de su e ciencia y la comparacin con un algoritmo de ordena-
intercambindolos de forma que a continuacin estn en la zona de la particin que
les corresponde. La iteracin nalizar cuando no haya elementos descolocados.
El algoritmo de particin propuesto por Weiss es el siguiente:
cin de los llamados lentos. Tambin deberis implementar una versin re nada de
Quicksort, para comparar su e ciencia con la primera versin estudiada. El cdigo
ya implementado que se referencia en los siguientes puntos, lo podris encontrar en
el subdirectorio
{ fin - ini + 1 >= 3 }
algoritmo particin(v:vector; ini,fin:entero);
{ Particin de v entre ini y fin }
var izq,der:entero; pivote:tipobase fvar
prac2
de
/practicas/asignaturas/ad3alum.
6.1 Estudio experimental de la e ciencia de Quicksort y comparacin con el algoritmo de Insercin directa
Deberis comparar el algoritmo diseado con un algoritmo de ordenacin de coste
cuadrtico, como es en promedio Insercin directa. Estos algoritmos se os proporcionarn ya implementados. El mtodo a seguir ser el siguiente:
Deberis medir el tiempo de ejecucin de cada uno de los algoritmos en funcin
ptimo de recursin, por debajo del cual se ordene el subvector mediante Inser-
de la talla, para un rango de tallas entre 500 y 5000, a intervalos de 500.
cin directa. Una estimacin analtica de dicho umbral necesitara medidas del
Para cada talla estudiada, mediris los tiempos de ejecucin sobre un determinado nmero de instancias de prueba, que se pueden generar de forma aleatoria
con los procedimientos del mdulo
genera
ya implementado. Promediaris el
tiempo de ejecucin de este conjunto de instancias.
de esta medida.
La salida del programa debe ser en forma de chero de texto, de forma que en
cada lnea aparezcan los datos correspondientes a una talla
determinar las constantes que aparecen en los costes en ese rango de tallas.
Pero estos tiempos son menores que la precisin del reloj del sistema. Disead
un experimento en el que se puedan obtener tiempos de ejecucin signi cativos
para tallas entre 20 y 100, basndose en repetir, para cada talla e instancia, los
El tiempo de ejecucin se podr calcular utilizando la rutina clock de la
librera del lenguaje C. En el anexo A se presentan los detalles de obtencin
tiempo de ejecucin de Insercin directa y de Particin con tallas bajas, para
n:
procedimientos un nmero de veces su cientemente grande.
El mtodo pro-
puesto deber tener en cuenta que, despus de ejecutar una vez la ordenacin,
el vector queda ya ordenado.
3. Un mtodo ms directo y able para estimar el umbral ptimo de recursin,
consiste en calcularlo experimentalmente. Proponed un experimento que determine un umbral ptimo de recursin, y que al mismo tiempo indique la mejora
de tiempos que se puede obtener para tallas del orden de 5000. Como hiptesis
n tiempo_quicksort tiempo_insercin_directa
de partida, suponed que el umbral buscado estar como mucho en
Estos datos se pueden procesar con el comando t de ajuste por mnimos
cuadrados del programa "gnuplot". Las curvas ajustadas obtenidas se pueden
representar gr camente con el comando "plot" del mismo programa
6.2 In uencia del comportamiento de la particin en el algoritmo
Quicksort
como muy poco en
n = 25,
n = 2.
4. Cul es el mximo nmero de intercambios de elementos que pueden llegar a
hacer, respectivamente, la particin de la seccin 2 y de la seccin 5, sobre un
vector de talla
n?
A qu instancia corresponde en cada caso?
5. A qu instancia corresponde el comportamiento cuadrtico de Quicksort cuando usa la particin de la seccin 2?
Siguiendo el mtodo descrito en el apartado anterior, deberis comparar el comportamiento temporal del algoritmo Quicksort con dos versiones diferentes de la particin.
Para ello, implementaris el algoritmo Quicksort usando como particin la de
Weiss, descrita en la seccin 5.
Esta particin slo es aplicable a vectores de tres
o ms elementos, por lo que en esta implementacin de Quicksort, el caso general
del algoritmo se dar cuando
ini + 1 < f in.
Deberis cambiar el caso base coheren-
temente. Deberis comprobar que el algoritmo funciona correctamente.
Para ello,
probad con diferentes instancias (vector ya ordenado de forma creciente, vector ya
6. Discutid el coste espacial de Quicksort en el caso mejor y en el caso peor.
7. Suponed que se modi ca el algoritmo de particin de Weiss sustituyendo las
lneas 3 y 4 por las siguientes:
(3) repetir izq:=izq+1 hasta (v[izq]>pivote) o (izq=fin-2);
(4) repetir der:=der-1 hasta (v[der]<pivote) o (der=ini+1);
ordenado de forma decreciente, vector con elementos iguales,...) y con un nmero de
de forma que el intercambio entre dos elementos se produzca solamente cuando
elementos conveniente para hacer una traza.
estos son distintos al pivote.
Deberis comparar los tiempos de ejecucin de esta versin de Quicksort, con los
de la versin del apartado 6.1.
Para este experimento, se recomienda extender el
rango de tallas a estudiar hasta 15000.
Considerando como entrada un vector en el que todos los elementos son iguales,
comparad el algoritmo original y el propuesto:
(a) Estudiando el nmero de intercambios realizados.
7 Cuestiones
(b) La posicin nal del pivote.
1. Suponiendo que las curvas obtenidas para el comportamiento temporal de Insercin directa y de Quicksort (en sus dos versiones), en las actividades 6.1 y
6.2 se pudiesen extrapolar a grandes tallas, cul sera el tiempo de ejecucin
que se podra esperar en promedio para cada uno de los tres algoritmos, con
5
vectores del orden de 10 elementos?
2. Un estudio para tallas bajas (menores que 50) de Insercin directa y de Quicksort, revela que el mejor comportamiento del segundo se mani esta tempranamente. An as, se puede mejorar su comportamiento buscando un umbral
Cul es el tiempo de ejecucin de Quicksort con cada algoritmo ante la entrada
considerada?
8. Suponed que se implementa el algoritmo
mediana3
v[ini], v[f in]
empezando izq
Determinar la mediana de
v[f in].
Ejecutar particin
adems, que
v[0] = ,
(a) Dada la entrada
como sigue:
v[centro],
en ini y der
y
intercambindola con
en
f in 1.
Suponed,
de modo que hay un centinela.
2, 3, 4, ..., n 1, n, 1,
esta versin de Quicksort?
10
cul es el tiempo de ejecucin de
(b) Dada la entrada
n, n 1, ...4, 3, 2, 1,
cul es el tiempo de ejecucin de
esta versin de Quicksort?
9. En el algoritmo de particin debido a Weiss se esconde el pivote en la posicin
f in 1
para ser posteriormente restaurado.
de? Para ello demuestra que al nalizar particin se cumple que
ini <
Cmo deberan ser las llamadas recursivas que se efectan en
Quicksort utilizando este algoritmo de particin?
que tambin puede afectar al pivote), el algoritmo de particin se puede modi car para que el vector se particione en tres zonas: elementos menores que
y elementos mayores que
Un estudio temporal de ambas particiones, efectuado con una entrada aleatoria
de caractersticas similares a las de esta prctica, para tallas entre 5000 y 50000
un comportamiento uniformemente mejor (aproximadamente en un 3%) que la
de Weiss.
Un estudio temporal de Quicksort utilizando ambas particiones, en condiciones
particin debida a Weiss presentaba un comportamiento uniformemente mejor
10. Si es probable que en el vector a ordenar aparezcan elementos repetidos, (lo
para evitar que el recorrido de izquierda a
similares a las enunciadas, mostr sin embargo que el algoritmo que utilizaba la
(b) Por qu crees que se esconde el pivote?
elementos iguales a
N + 1,
(10000 instancias para cada talla), demostr que la particin de Dijkstra tena
(a) Sigue siendo correcto el algoritmo particin si el pivote no se escon-
izq f in.
un centinela en la posicin
derecha se salga de rango.
p.
p,
Escribid un algoritmo que
realice esta particin. Cul sera el comportamiento de Quicksort en el caso
(aproximadamente en un 10%) que el algoritmo que utilizaba la particin de
Dijkstra.
La siguiente tabla muestra otros resultados obtenidos en el estudio experimental de los algoritmos de particin de Weiss (parW) y el de Dijkstra (parD).
Para cada algoritmo, la columna
pos
representa la posicin que, en trmino
medio, ocupa el pivote tras la particin. Tambin, como ndice de desviacin
mejor con esta nueva particin?
de las medidas con respecto a la posicin central, se ha representado columnas
11. El algoritmo de particin siguiente fue propuesto por Dijkstra [Sedgewick,78]:
desv
la desviacin estndar de las medidas efectuadas con respecto a la posi-
cin central.
{ v[N+1] = +infinito }
algoritmo particinD(v:vector; ini,fin:entero);
{ Particin de v entre ini y fin, segn Dijkstra }
var izq,der:entero; pivote:tipobase fvar
pivote := v[ini];
izq:=ini+1; der:=fin;
repetir
mientras v[izq]<pivote hacer izq:=izq+1 fmientras;
mientras v[der]>pivote hacer der:=der-1 fmientras;
si izq <= der entonces
intercambiar v[izq] y v[der]
izq:=izq+1; der:=der+1
fsi
hasta der < izq;
intercambiar v[ini] y v[der] { restaura el pivote }
fparticinD
talla
pos(parW)
pos(parD)
5000
10000
15000
20000
25000
30000
35000
40000
45000
50000
2516
4979
7494
9912
12489
15030
17543
19833
22751
25054
2477
4994
7506
10023
12415
14997
17508
20158
22587
24727
desv(parW) desv(parD)
1115
2235
3396
4450
5575
6708
7822
8930
10153
11104
1443
2881
4322
5788
7139
8641
10091
11536
13073
14307
Hay diferencias signi cativas entre las posiciones devueltas por ambas particiones?, y entre las medidas de desviacin estndar? Qu deduces de los
resultados?
Referencias
[1] C. A. R. Hoare, Quicksort, Computer Journal, Vol. 5 (4), 1962.
El algoritmo se basa en una estrategia de intercambio similar a la del algoritmo
de Weiss: slo se intercambian dos elementos cuando ambos son, respectivamente, mayor o igual que el pivote y menor o igual que el pivote. La principal
diferencia reside en el criterio de eleccin del pivote, que en el algoritmo de
[2] R. Sedgewick, Implementing Quicksort Programas, Communications of ACM,
Vol. 21 (10), 1978.
[3] M. A. Weiss, Estructuras de datos y algoritmos, Addison-Wesley Iberoamericana, 1995.
Dijkstra es el elemento ms a la izquierda. En la nueva particin se necesita
11
12
A Compilacin: makefile
El comando
make
bash_> gnuplot
G N U P L O T
Linux version 3.5 (pre 3.6)
patchlevel beta 347
last modified Mon Jun 22 13:22:33 BST 1998
est pensado para facilitar el mantenimiento y regeneracin de
grupos de programas. En particular, es muy til cuando un programa est distribuido
en varios cheros. En este caso, el programador crea un chero (llamado
makefile
por defecto) en el que se de nen las dependencias entre los diferentes cheros del
programa. Cada vez que se ejecuta el comando
make se examina
el chero
makefile
Copyright(C) 1986 - 1993, 1998
Thomas Williams, Colin Kelley and many others
para determinar las dependencias entre los distintos cheros que forman el programa.
Con esta informacin, el comando
make recompilar
aquellos cheros fuente que han
sido modi cados con posterioridad a la generacin de su cdigo objeto y, a su vez,
Send comments and requests for help to [email protected]
Send bugs, suggestions and mods to
[email protected]los que dependen de stos.
La utilizacin del comando
make
tiene, pues, dos consecuencias:
en cada momento, nicamente se recompila lo que es estrictamente necesario y
se evita el error (muy frecuente) de olvidarse de recompilar algn chero fuente
Terminal type set to 'x11'
gnuplot>
que haya sido modi cado o que dependa de alguno que haya sido modi cado,
Cuando lo utilices en este modo recuerda que dispones de ayuda on-line accesible
adems de ejecutar la compilacin en orden correcto.
Como ejemplo, supongamos que tenemos creado el chero
makefile,
con "help" y que sales del mismo con "quit".
cuyo con-
tenido es:
prg: modulo.o prg.c
gcc -o prg prg.c modulo.o
modulo.o: modulo.c
gcc -c modulo.c
Cuando el usuario ejecuta el comando
depende de los cheros
prg.c modulo.o (si
modulo.o, y la lnea
modulo.o y prg.c.
make,
prg, que
gcc -o prg
se genera el ejecutable
Automticamente, se ejecuta
es necesario). La lnea tercera indica de qu cheros depende
cuarta cmo se genera (si es necesario).
nom_var dentro de un chero makefile y despus
$(nom_var). Por ejemplo, el chero anterior podra ser:
Se puede de nir una variable
utilizar su contenido con
Si deseamos dibujar una curva a partir de las dos primeras columnas, con la primera
columna como abcisa, y la segunda como ordenada, entonces la orden apropiada
seria:
signi ca
using
y indica que debe utilizarse la columna 1 para
w l signi ca with lines,
puntos con una lnea (hacer help plot para ver ms opciones).
esto es, que una los
Si deseamos mejorar
la presentacin, entoces puede hacerse:
B Visualizacin gr cas: gnuplot
es un dibujador de gr cas disponible para diversos sistemas operativos
como UNIX, MS-DOS y VMS. La documentacin sobre este programa incluye, entre
otros textos, un manual de referencia on-line.
13
0.01
0.02
0.02
0.05
0.07
0.08
0.11
En esta orden,
Por ltimo, las columnas donde se indican las rdenes a ejecutar deben comenzar
modo interactivo.
0.07
0.30
0.75
1.37
2.26
3.32
4.51
la abcisa, y la 2 para la ordenada.
con un tabulador, no con espacios.
Aunque existe la posibilidad de utilizarlo en batch,
100
200
300
400
500
600
700
f1.dat con el siguiente formato:
gnuplot> plot 'f1.dat' u 1:2 w l
nom = prg
$(nom): modulo.o $(nom).c
gcc -o $(nom) $(nom).c modulo.o
modulo.o: modulo.c
gcc -c modulo.c
gnuplot
Por ejemplo, imaginemos que tenemos un chero
gnuplot
suele utilizarse en
gnuplot>
gnuplot>
gnuplot>
gnuplot>
set xlabel "Size"
set ylabel "Time"
set title "Algorithm A"
plot 'f1.dat' u 1:2 w l
La gr ca obtenida con esta secuencia de comandos del
gnuplot
se ilustra en la
gura 1.
El programa
gnuplot
permite hacer ajustes por mnimos cuadrados de un con-
junto de datos. Por ejemplo, si deseamos hacer una ajuste por mnimos cuadrados
de los datos anteriores, podemos hacer:
14
Algorithm A
Algorithm A
5
kk u 1:2
f(x)
f1.dat u 1:2
4.5
4.5
3.5
3.5
3
2.5
Time
Time
3
2.5
2
1.5
1.5
0.5
0.5
0
100
200
300
400
Size
500
Figura 1: Ejemplo de la salida generada por
gnuplot>
gnuplot>
...
gnuplot>
gnuplot>
gnuplot>
gnuplot>
600
700
gnuplot.
gnuplot.
por ejemplo el siguiente fragmento de programa Pascal:
La orden para
cl1:=clock;
S;
cl2:= clock;
cl3:=cl2-cl1;
via aparecen los parmetros de
fit produce una salida que informa sobre
help fit para interpretar estos resultados). La
C Medida del coste computacional: primitiva clock
Una forma de medir el coste computacional necesario para la ejecucin de un programa o segmento del mismo, consiste en contar el nmero de veces que se realiza
algn tipo de operacin signi cativa (comparaciones, productos, productos aditivos,
). Otra forma es utilizar alguna rutina del sistema que mida tiempos de eje-
cucin. Es importante sealar que si se trabaja en un sistema de tiempo compartido,
las medidas que se realicen debern ser independientes de la carga del sistema.
El sistema operativo UNIX lleva una cuenta para cada proceso y, en cada momento, del nmero de ticks de CPU consumidos. Estos ticks equivalen generalmente a
donde
{instruccin 1}
{instruccin 2}
es cualquier instruccin. El cdigo en C sera anlogo, teniendo en cuenta
que la llamada a la funcin de reloj debe explicitar la lista vaca de argumentos:
clock().
Despus de la ejecucin de este fragmento de programa tendremos:
cl1
tiempo de proceso consumido hasta la instruccin 1 (en ticks).
cl2
tiempo de proceso consumido hasta la instruccin 2 (en ticks).
cl3
tiempo de proceso consumido para la instruccin
clock
(de la librera
(en ticks) .
Hay que tener cuidado en la colocacin de las instrucciones de temporizacin, ya
que se debe evitar incluir entre ellas toda aquella parte del cdigo que no se desee
temporizar.
una pequea cantidad de tiempo (del orden de microsegundos). En Pascal y C es po-
15
700
Una llamada a esta funcin (sin argumentos), devuelve un entero que es propor-
En esta orden, despus de
sible determinar este nmero haciendo uso de la rutina
600
cional a la cantidad de tiempo de procesador utilizado por proceso en curso. As, sea
salida que se produce en este caso puede verse en la gura 2.
...
500
function clock: integer; C;
la funcin que se desea modi car. La orden
etc
400
Size
del lenguaje C). En el caso de Pascal, se debe incluir en el espacio del programa
Primero de nimos la funcin a la que se desea ajustar los datos.
las caractersticas del ajuste (hacer
300
reservado para la declaracin de procedimientos y funciones:
set xlabel "Size"
set ylabel "Time"
set title "Algorithm A"
plot f(x),'f1.dat' u 1:2 w l
fit.
200
Figura 2: Ejemplo de ajuste por mnimos cuadrados producido por
f(x)=a*x+b
fit f(x) 'f1.dat' via a,b u 1:2
realizar el ajuste es
-0.5
100
time.h
16
