Scribd
Cargar
26 vistas7 páginas

Quicksort

Quicksort es un algoritmo de ordenamiento basado en el paradigma 'dividir y conquistar', que divide un arreglo en sub-arreglos y los ordena recursivamente. El rendimiento de Quicksort varía entre O(n^2) en el peor caso y O(n log n) en el mejor y promedio, dependiendo de cómo se realice la partición. Una versión aleatorizada del algoritmo mejora su desempeño al seleccionar un pivote aleatorio, evitando peores casos en entradas no aleatorias.

Cargado por

dfjar
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPT, PDF, TXT o lee en línea desde Scribd
26 vistas7 páginas

Quicksort

Quicksort es un algoritmo de ordenamiento basado en el paradigma 'dividir y conquistar', que divide un arreglo en sub-arreglos y los ordena recursivamente. El rendimiento de Quicksort varía entre O(n^2) en el peor caso y O(n log n) en el mejor y promedio, dependiendo de cómo se realice la partición. Una versión aleatorizada del algoritmo mejora su desempeño al seleccionar un pivote aleatorio, evitando peores casos en entradas no aleatorias.

Cargado por

dfjar
Derechos de autor
© © All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como PPT, PDF, TXT o lee en línea desde Scribd

Quicksort

Agustín J. González
ELO320: Estructura de Datos y
Algoritmos
1er. Sem. 2002

1
Quicksort Descripción
• 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
Quicksort(A,p,r){ Partition(A,p,r) {
if (p<r) { x=A[p];
q = Partition(A,p,r); i=p-1;
Quicksort(A,p,q); j=r+1;
Quicksort(A,q+1, r); while(1) {
} do j--;
} until (A[j]  x)
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 que
A[p] en la región inferior del arreglo y los elementos mayores.
• 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.
• Cuando estos elementos son encontrados, son intercambiados.
• Si estos elementos no son encontrados, i terminará por igualar 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
i j j i Retorna j 4
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   (n 2 )
 k 1 
• 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
log10 n
n/10 9n/10 n

n/100 9n/100 9n/100 81n/100 n

n
1
n

log10 / 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 aun 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);
}
}

También podría gustarte