26/01/2018
QUICKSORT
Presentación basada en la lecture de Tim
Roughgarden Univ. Stanford.
Quicksort
Algoritmo de ordenamiento.
Tiempo “promedio” de ordenamiento O(n log n).
A diferencia de Mergesort trabaja sin ocupar
espacio adicional.
Problema de ordenar
Entrada: Un arreglo de n números desordenado.
3 8 2 5 1 4 7 6
Salida: los mismos números ordenados en orden
creciente.
1 2 3 4 5 6 7 8
Se asume que todas las entradas del arreglo son
distintas.
1
26/01/2018
Descripción general del algoritmo
Quicksort (arreglo A, longitud n)
Si n=1 return
P=selecionarPivote(A,n)
Particionar A alrededor de P
A <P P >P
1ª parte 2ª parte
Recursivamente ordenar 1ª parte
Recursivamente ordenar 2ª parte
Particionar alrededor de un pivote
Idea principal: Particionar el arreglo alrededor de
un elemento pivote
3 8 2 5 1 4 7 6
Seleccionar un elemento del arreglo
Reordenar el arreglo de manera que:
A la izquierda del pivote estén los elementos menores a él.
A la derecha del pivote estén los elementos mayores a él.
2 1 3 6 7 4 5 8
Nota: Pone el pivote en su posición “correcta”.
Acerca de la partición
Esta se puede hacer en un tiempo lineal O(n), sin memoria
adicional.
Reduce el tamaño del problema.
La manera fácil de hacerlo en O(n) pero utilizando memoria
adicional.
3 8 2 5 1 4 7 6
2 1 5 8
Comenzamos a recorrer los elementos y si es menor al pivote lo
colocamos al inicio del arreglo y si es mayor al final. Entonces los
primeros elementos del arreglo son < pivote y la últimos son >
pivote.
2
26/01/2018
Partición en el lugar
Asumamos que el pivote es el primer elemento de
arreglo. (Sino hagamos un swap del pivote con el
primer elemento de manera anticipada).
Idea general:
P <P >P ?
Ya particionado Sin particionarse
Ejemplo de partición
swap
3 8 2 5 1 4 7 6 3 8 2 5 1 4 7 6
i, j Sin partición i particionado j Sin partición
3 2 8 5 1 4 7 6 3 2 8 5 1 4 7 6
i particionado j Sin partición i particionado j Sin partición
swap
3 2 8 5 1 4 7 6 3 2 1 5 8 4 7 6
i particionado j Sin partición i particionado j Sin partición
P <P >P ?
i j
Ejemplo de partición (cont)
swap
3 2 1 5 8 4 7 6 1 2 3 5 8 4 7 6
i particionado j <3 >3
3
26/01/2018
Pseudocódigo para la partición
Particionar(A, l, r)
p = A[ l ]
i=l+1
for j =l + 1 to r
If A[ j ] < p
swap A [ i ] y A[ j ]
i ++
swap A[ l ] y A [ i – 1 ]
La importancia del pivote
¿Cuál es el tiempo de ejecución de Quicksort?
Depende de la “calidad” del pivote
Supongamos que siempre seleccionamos el primer
elemento del arreglo. ¿Cuál el tiempo de ejecución
de este algoritmo en un arreglo que ya está
ordenado?
𝜃(𝑛2 )
A <P P >P
vacío Longitud n-1
(continua ordenado)
La importancia del pivote
Supongamos que mágicamente seleccionamos en
cada llamada recursiva el elemento de la mitad del
subarreglo. ¿Cuál el tiempo de ejecución de este
algoritmo en un arreglo?
𝜃(𝑛 log 𝑛)
4
26/01/2018
Selección del pivote
Pregunta clave: ¿Cómo seleccionamos los pivotes?
Gran idea!!!!
De manera aleatoria.
Esperanza: Un pivote aleatorio es “suficientemente
bueno frecuentemente”
Intuición:
Si siempre tenemos una partición 25-75, es suficiente
para alcanzar un desempeño de O(n log n)
Si tenemos los números de 1 al 100 entonces la mitad
de los elementos nos dará una partición 25-75 o mejor.
