Quicksort viernes, 13 de septiembre de 2024

Quicksort Quicksort
El algoritmo Quicksort se utiliza para Las constantes dentro de la notación
ordenar números. Su peor tiempo de  son pequeñas.
ejecución es n 2 u.t. para una entrada
El algoritmo Quicksort utiliza el
de n números.
paradigma divide y vencerás. Este
Una propiedad muy importante del paradigma se puede separar en tres
algoritmo Quicksort es que su tiempo de partes:
ejecución promedio es n log n u.t.

Departamento de Ciencias de la Computación 1 Departamento de Ciencias de la Computación 2

Dividir Conquistar
Dividir: Se divide el arreglo Ap … r en dos
subarreglos Ap … q 1 y Aq 1… r. Conquistar: Los dos subarreglos
Ap … q 1 y Aq 1… r se ordenan en
Cada elemento del arreglo Ap … q 1 es
menor o igual que Aq y, por consiguiente,
forma recursiva utilizando el mismo
menor o igual que cualquier elemento del algoritmo Quicksort.
arreglo Aq 1… r.
Se calcula el índice q en este paso.

Departamento de Ciencias de la Computación 3 Departamento de Ciencias de la Computación 4

Combinar Quicksort
Un pseudo-código de este algoritmo se
Combinar: Debido a que los subarreglos
muestra a continuación:
están ordenados en el lugar correcto,
no es necesario realizar ninguna
operación adicional. Por lo tanto, el
arreglo Ap … r está ordenado.

Departamento de Ciencias de la Computación 5 Departamento de Ciencias de la Computación 6

Análisis de Algoritmos - notas # 6 1

Quicksort viernes, 13 de septiembre de 2024

Partición Partición
p r

2 8 7 1 3 5 6 4

i j

Departamento de Ciencias de la Computación 7 Departamento de Ciencias de la Computación 8

Partición Partición
p r p r

2 8 7 1 3 5 6 4 2 8 7 1 3 5 6 4

i j i j

Departamento de Ciencias de la Computación 9 Departamento de Ciencias de la Computación 10

Partición Partición
p r p r

2 8 7 1 3 5 6 4 2 1 7 8 3 5 6 4

i j i j

Departamento de Ciencias de la Computación 11 Departamento de Ciencias de la Computación 12

Análisis de Algoritmos - notas # 6 2

Quicksort viernes, 13 de septiembre de 2024

Partición Partición
p r p r

2 1 3 8 7 5 6 4 2 1 3 8 7 5 6 4

i j i j

Departamento de Ciencias de la Computación 13 Departamento de Ciencias de la Computación 14

Partición Partición
p r p r

2 1 3 8 7 5 6 4 2 1 3 4 7 5 6 8

i j i j

Departamento de Ciencias de la Computación 15 Departamento de Ciencias de la Computación 16

Invariante de lazo Inicialización

La invariante de lazo del procedimiento
Antes de la primera iteración del ciclo,
PARTITION es:
i  p  1 y j  p. No existe ningún índice
Al principio de cada iteración j del ciclo entre p e i, y tampoco entre i  1 y j  1,
for líneas 3-6, para cualquier índice k por lo que las primeras dos condiciones de
del arreglo: la invariante de lazo se cumplen.
1. Si p  k  i, entonces A k   x.
La asignación de la línea 1 satisface la
2. Si i 1  k  j  1, entonces A k   x. condición 3.
3. Si k  r, entonces A k   x.
Departamento de Ciencias de la Computación 17 Departamento de Ciencias de la Computación 18

Análisis de Algoritmos - notas # 6 3

Quicksort viernes, 13 de septiembre de 2024

Mantenimiento Mantenimiento
Existen dos casos que dependen de la
p i j r
salida de la comparación de la línea 4.
x x
Caso 1. Cuando A  j   x:
Únicamente se incrementa j. Después de x x
incrementarse j, la condición 2 se man-
tiene para A  j1 y todos los otros valores p i j r
se mantienen sin cambio ver la siguiente x
figura.
x x
Departamento de Ciencias de la Computación 19 Departamento de Ciencias de la Computación 20

Mantenimiento Mantenimiento
Caso 2. Cuando A  j   x :
El índice i se incrementa, A i y A  j se in- p i j r
tercambian y después j se incrementa. x x
Debido al intercambio, Ai  x, lo que sa-
x x
tisface la condición 1.
Similarmente, A  j1  x ya que el elemento
p i j r
que se metió a A  j1 ya era mayor que x
x
por la invariante de lazo de la iteración
anterior. x x
Departamento de Ciencias de la Computación 21 Departamento de Ciencias de la Computación 22

Finalización Desempeño del quicksort

Al final del ciclo j  r, y por lo tanto cada El peor caso del algoritmo ocurre cuando
elemento del arreglo está en alguno de los la rutina de partición genera un arreglo
tres subconjuntos especificados en la de un elemento y otro de n  1 elementos.
invariante de lazo: Aquellos que son me- Si esta situación se genera en cada
nores iguales a x; los que son mayores que iteración, entonces el tiempo de ejecución
x; un elemento solo que corresponde a x. está dado por la siguiente recursión
p i r j
T ( n)  T (n  1)  (n)
x
en donde
x x
T (1)  (1)
Departamento de Ciencias de la Computación 23 Departamento de Ciencias de la Computación 24

Análisis de Algoritmos - notas # 6 4

Quicksort viernes, 13 de septiembre de 2024

Partición desbalanceada Partición desbalanceada

n
Resolviendo la recursión,
1 n-1
n
 n 
1 n-2 T (n)   ( k )
k 1
   k   (n 2 )
 k 1 
n 1 n-3
n
n (n  1)
1 Nota. recuerde que: k 
2
2 k 1

1 1

Departamento de Ciencias de la Computación 25 Departamento de Ciencias de la Computación 26

Mejor caso Partición balanceada

El mejor caso ocurre cuando la
n
partición es balanceada, esto es cuando
el arreglo de n elementos se parte en n/2 n/2
dos subarreglos de n/2 elementos y así
n/4 n/4 n/4 n/4
sucesivamente. El tiempo de ejecución log n
está dado por la siguiente recursión:
T (n)  2 T (n / 2)  (n)
cuya solución es: 1111111111111111111111111111
T ( n)  ( n log n)
Departamento de Ciencias de la Computación 27 Departamento de Ciencias de la Computación 28

Partición desbalanceada constante Partición desbalanceada constante

Ejemplo:
Si la partición del arreglo es desbalan-
ceada pero se mantiene siempre una Si la partición en la primera iteración
relación constante entre los bloques de se hace 1/10n y 9/10n, el número
ella, entonces el tiempo de ejecución de iteraciones es log10/9 n  O log n.
sigue siendo O n log n. De aquí que el tiempo de ejecución sea
O n log n.

Departamento de Ciencias de la Computación 29 Departamento de Ciencias de la Computación 30

Análisis de Algoritmos - notas # 6 5

Quicksort viernes, 13 de septiembre de 2024

Partición desbalanceada constante Dependencia de la entrada

n  Note que, hasta este momento, el tiempo

1/10n 9/10n
de ejecución depende de qué elemento se
log10 n tome como pivote. Como siempre se toma
1/100n 9/100n 9/100n 81/100n
al último elemento del arreglo como el
log10/9 n
pivote, entonces el tiempo de ejecución
729/1000n
1 depende del orden que tenga la entrada.

Departamento de Ciencias de la Computación 31 Departamento de Ciencias de la Computación 32

Dependencia de la entrada Dependencia de la entrada

 Algo curioso con el quicksort es que La suposición anterior no siempre es
cuando la entrada está completamente buena para muchas aplicaciones.
ordenada, el tiempo de ejecución es el
Ejemplo: Los bancos mantienen un
peor de los casos, O n 2 u.t.
registro de los cheques de acuerdo al
 Si se supone que el orden de la entrada orden en el que fueron cobrados, pero
puede ser cualquiera, con igual muchas personas prefieren recibir
probabilidad, entonces esta implantación estados de cuenta que vengan ordenados
del quicksort tiene buen desempeño. de acuerdo al número de cheque.
Departamento de Ciencias de la Computación 33 Departamento de Ciencias de la Computación 34

Dependencia de la entrada Dependencia de la entrada

Las personas normalmente usan sus Si el banco tiene los cheques ordenados
cheques de acuerdo al número de por fecha de cobro, reordenarlos de
cheque, pero los comerciantes no acuerdo al número de cheque implica el uso
de algún algoritmo de ordenamiento cuya
siempre cobran los cheques inmedia-
entrada es una secuencia casi ordenada.
tamente, así que los números de
La versión previa del quicksort quizá no
cheques no siempre coinciden con el
sea la más adecuada, y algoritmos como el
tiempo de cobro.
“Insertion-sort” sea más conveniente.

Departamento de Ciencias de la Computación 35 Departamento de Ciencias de la Computación 36

Análisis de Algoritmos - notas # 6 6

Quicksort viernes, 13 de septiembre de 2024

Eliminando la dependencia Eliminando la dependencia

 Una alternativa para evitar la suposi-
ción de que la distribución de  Un procedimiento de este tipo se puede
probabilidad de la entrada es uniforme, hacer en O n u.t.
es imponer una nueva distribución.  La ventaja de incluir este procedimiento
 Esto se puede hacer si el quicksort, es que el tiempo de ejecución se hace
previo a su ejecución, permuta en independiente del orden de la entrada.
forma aleatoria a los elementos de la
entrada.

Departamento de Ciencias de la Computación 37 Departamento de Ciencias de la Computación 38

Generador aleatorio Generador aleatorio

 Se supone que se posee un generador  Se supone que el número aleatorio

de números aleatorios. generado en un instante dado es
independiente de los números
 Una llamada a la función RANDOMa,b
generados con anterioridad.
regresa un entero del intervalo a,b,
cada uno con igual probabilidad. Ejemplo: RANDOM0,1 es un generador
aleatorio de bits, cada bit tiene
probabilidad de ocurrencia de ½.

Departamento de Ciencias de la Computación 39 Departamento de Ciencias de la Computación 40

Generador aleatorio Quicksort aleatorio

RANDOMIZED-PARTITION A,p,r
A pesar de que no existen generadores 1. i  RANDOM p,r
perfectos de números aleatorios, en 2. exchange A r ↔ A i 
general, los algoritmos aleatorios tienen un 3. return PARTITION A,p,r
buen desempeño con los pseudo generadores
RANDOMIZED-QUICKSORT A,p,r
aleatorios que se usan en la práctica.
1. If p  r then
La versión aleatoria del quicksort se 2. q  RANDOMIZED-PARTITION A,p,r
3. RANDOMIZED-QUICKSORT A,p,q 1
presenta en el pseudo código siguiente:
4. RANDOMIZED-QUICKSORT A,q 1,r

Departamento de Ciencias de la Computación 41 Departamento de Ciencias de la Computación 42

Análisis de Algoritmos - notas # 6 7

Quicksort viernes, 13 de septiembre de 2024

Quicksort aleatorio Quicksort aleatorio

 La parte del algoritmo que consume más  Se puede demostrar que el tiempo de
tiempo es la que corresponde a la ejecución esperado del algoritmo quicksort
partición del arreglo en subarreglos. aleatorio es O n log n pasos.
Dicha demostración se discute en el curso
 El tiempo de ejecución de esta rutina Algoritmos aleatorios que se imparte en el
es directamente proporcional al número segundo o tercer cuatrimestre.
de comparaciones que realiza.

Departamento de Ciencias de la Computación 43 Departamento de Ciencias de la Computación 44

Análisis de Algoritmos - notas # 6 8