Quicksort
Agustín J. González
ELO320: Estructura de Datos y
Algoritmos
1er. Sem. 2004
1
Descripción de Quicksort
Quicksort, como Mergesort, está basado en el paradigma “dividir y
conquistar”.
Pasos:
Dividir: el arreglo se particiona en dos sub-arreglos no vacíos, tal
que cada elemento de un sub-arreglo sea menor o igual a los
elementos del otro sub-arreglo.
Conquistar: los dos arreglos son ordenados llamando
recursivamente a quicksort.
Combinar: Como cada arreglo ya está ordenado, no serequiere
trabajo adicional.
Algoritmo
Quicksor(A,p,r){
if (p<r) {
q = Partition(A,p,r);
Quicksort(A,p,q);
Quicksort(A,q+1, r);
}
} 2
Partition
Partition(A,p,r) {
x=A[p];
i=p-1;
Quicksort(A,p,r){ j=r+1;
if (p<r) { while(1) {
q = Partition(A,p,r); do j--;
Quicksort(A,p,q); until (A[j] x)
Quicksort(A,q+1, r); do i++;
} until (A[i] x)
} if (i < j)
exchange A[i] <-> A[j];
else
return j;
}
}
3
Explicación
Partition efectúa una tarea simple: poner los elementos menores o igual que A[p]
en la región inferior del arreglo y los elementos mayores o igual al otro lado..
i parte del extremo inferior del arreglo y j parte del extremo superior.
Cada puntero avanza hacia el extremo opuesto buscando elementos que deba
mover hacia el otro extremo. j se acerca primero. ¿Cambia si i lo hace primero?
Cuando estos elementos son encontrados, son intercambiados.
Si estos elementos no son encontrados, i terminará igual o superior a j.
5|3|2|6|4|1|3|7 5|3|2|6|4|1|3|7
i j i j
3|3|2|6|4|1|5|7 3|3|2|6|4|1|5|7
i j i j
3|3|2|1|4|6|5|7 3|3|2|1|4|6|5|7
j j i Retorna j 4
i
Observaciones
Los índices i y j nunca acceden al arreglo fuera de rango.
A[p] debe ser el “pivote”. Si se tomara A[r] y ocurre que éste es el
mayor valor, Partition retornaría q=r y Quicksort estaría en un loop
infinito.
Rendimiento de Quicksort:
Partition tiene costo (n).
Partición de peor caso:
Ocurre cuando el arreglo es particionado en n-1 y 1 elemento cada vez.
En este caso se tiene: T(n)=T(n-1) + (n) =
n
n
k 1
( k ) k
k 1
( n 2
)
Partición de mejor caso:
Ocurre cuando Partition produce dos regiones de igual tamaño.
En este caso se tiene: T(n)=2T(n/2)+ (n) ,
de lo cual resulta T(n) = (n lg n) (caso 2 teorema maestro)
5
Observaciones
Si consideramos que la partición conduce a arreglos
desbalanceados en proporción 9 : 1, de todas formas el
algoritmo toma tiempo (n lg n).
En este caso T(n) = T(9n/10) +T(n/10) + (n)
n n
log 10 n
n/10 9n/10 n
n/100 9n/100 9n/100 81n/100 n
n
1
n
log 10 / 9 n (lg n) 1
(n lg n)
El caso promedio también conduce a tiempos (n lg n). 6
Versión “Aleatorizada” de Quicksort
Objetivo: Lograr buen desempeño aún cuando la entrada no sea
aleatoria.
Idea: Tomar aleatoriamente un elemento dentro del arreglo y
usarlo como pivote.
Randomized_Partition(A,p,r) {
i = random(p,r); /* retorna un valor en el rango [p,r] */
exchange A[p] <--> A[i];
return Partition(A, p, r);
}
Ramdomized_Quicksort(A,p,r) {
if (p < r) {
q = Randomized_Partition(A,p,r);
Randimized_Quicksort(A, p, q);
Randomized_Quicksort(A, q+1, r);
}
} 7
Partition codificado en C para
arreglos de enteros
int partition(int a[], int l, int r)
{ int left = l-1, right = r; int pivote = a[r];
for (;;)
{
while (a[++left] < pivote) ;
while ( pivote < a[--right]) if (right == l) break;
if (left >= right) break;
exch(a,left], right); /*a[left]<->a[right]*/
}
Obs: Esta
exch(a, left, r); /*a[left]<->a[r]*/implementación deja el
return left; pivote en la posición
} retornada. 8
Partition codificado en C para
arreglos de enteros
int partition(int a[], int l, int r);
void quicksort(int a[], int l, int r)
{ int i;
if (r <= l) return;
i = partition(a, l, r);
quicksort(a, l, i-1);
quicksort(a, i+1, r);
}
9
Comentarios Finales
Ojo que quicksort es O(n2) en el peor caso.
Quicksort no debería ser usado en sistemas
donde haya vidas en juego (sistemas
médicos) o misiones críticas (defensa,
monitoreo de planta nuclear).
En estos casos mejor usar heapsort!.
Lo mejor que podemos conseguir en
algoritmos de ordenamiento es O(nlgn).
Si sabemos algo sobre los datos es posible
encontrar soluciones mejores.
10
Divertimento
Sólo uno de estos caminos conduce a ciudad de la abundancia.
Un duende siempre miente. El otro siempre dice la verdad.
Con sólo una pregunta, ¿cómo sé que camino tomar?
11
