Clasificación Rápida Quicksort

TAREA CONCEPTUAL 5
NAYERI SUSETH LEMUS ACOSTA

31911847
Clasificación rápida Quicksort
El primer algoritmo O(nlogn) que se estudia y tal vez el mas eficiente para clasificación interna
recibe el nombre de clasificación rápida, la esencia del método consiste en clasificar un arreglo
A[1],….. A[n] tomando en el arreglo un valor clave y como elemento pivote alrededor del cual
reorganizar los elementos del arreglo. Es de esperar que el pivote este cercano al valor medio
de la clave del arreglo, de forma que este precedido por una mitad de las claves y seguido por
la otra mitad. Se permutan los elementos del arreglo con el fin de que para alguna j todos los
registros con claves menores que v aparezcan en A[1],….. A[j] y todos aquellos con clave v o
mayores en A[j+1],….. A[n].Después se aplica recursivamente la clasificación rápida a A[1],…….
A[j y a A[j+1],….. A[n]] para clasificar ambos grupos de elementos dados que todas las claves
del primer grupo proceden a todas las claves del segundo grupo, todo el arreglo quedara
ordenado.
Menores que el valor del pivote aparecen a la izquierda de las demás. Para realizar esto, se
introducen dos cursores, z y d en un principio en los extremos izquierdo y derecho
respectivamente de la porción de A que se esta clasificando. Los elementos a la izquierda de z
esto es A[i],…………A[z-1] siempre tendrán claves mayores o iguales al pivote y los elementos
del centro estarán mezclados como se muestra en la figura 8.12
En un comienzo i 0 z y j =d para que la proposición anterior se siga cumpliendo ya que no

existe nada a la izquierda de z ni a la derecha de d. se efectúan varias veces los pasos
siguientes los cuales mueven de z a la derecha y d a la izquierda hasta que terminen
cruzándose momentos en el que A[i],………….,A[z-1] tendrán todas las claves menores que el
pivote y A[d+1],……………..,A[j] todas las claves mayores o iguales que el pivote.
Tiempo de ejecución de la clasificación rápida

Ahora se mostrara que el algoritmo lleva en promedio un tiempo O(nlogn) para clasificar n
elementos y que en el peor caso lleva O(n2). El primer paso en la demostración de ambas
proposiciones es probar que partición lleva un tiempo proporcional al numero de elementos
que deberá separar es decir un tiempo O(j-i+1).
El tiempo total consumido por Quicksort es la suma en todos los elementos de las veces que el
elemento forma parte de la figura 8.9 donde se observan las llamadas a Quicksort, es evidente
que en ningún elemento puede incluirse dos llamados de mismo nivel, así que el tiempo
consumido por Quicksort puede expresarse como la suma en todos los elementos de la
profundidad o máximo nivel.
La profundidad de ri es n-i+1 para 2 <= i<=n, y la profundidad de r1 es n-1, así, la suma de la

profundidad es:
La cual es En el peor caso la clasificación rápida requiere un tiempo proporcional a n2

para clasificar n elementos.
Análisis del caso promedio de la clasificación rápida

Como siempre se interpreta caso promedio para un algoritmo de clasificación como el
promedio sobre todas las clasificaciones iniciales donde igual probabilidad a cualquier
clasificación posible. Por simplicidad se supondrá que no existen dos elementos con claves
iguales en general las igualdades entre elementos hacen la tarea de clasificación mas fácil,
nunca mas difícil.
Una segunda suposición que hace mas fácil el análisis del algoritmo de clasificación rápida es
que cuando se llama a Quicksort (i,j) todas las clasificaciones para A[I],……………………,A[J] son
igualmente probables. La justificación es que antes de la llamada no había pivotes con la cual
A[I],………….,A[J] se pudiera comparar para distinguirlos entre si; es decir para que todos fueran
menores que el pivote v o para que todos fueran mayores, una revisión cuidadosa del
programa desarrollado muestra la probabilidad de que cada elemento pivote concluya cerca
del extremo derecho del subarreglo de elementos mínimo el pivote previo pueda aparecer
cerca del extremo derecho no marca una diferencia considerable
Ahora sea T(n) el tiempo promedio consumido por la clasificación rápida para ordenar n
elementos es evidente que T(1) es alguna constante c1 ya que en un elemento esta
clasificación no hace llamadas recursivas a si mismas cuando n>1,se supone que todos los
elementos tienen clave distinta se sabe que la clasificación rápida tomara al pivote y dividirá el
subarreglos consumiendo un tiempo c2n para hacerlo para alguna constante c2.
Mejoras a la clasificación rápida

Quicksort es muy rápida su tiempo promedio de ejecución es menor que el de todos los
algoritmos de clasificación O(nlogn) conocidos en la actualidad es factible mejorar aun mas el
factor constante al tomar pivotes que dividan cada subarreglos en partes similares.
Otra mejora de la clasificación rápida esta relacionada con lo que sucede cuando se toman
subarreglos pequeños. Los métodos simples O(n2) son mejores que el método O(nlogn) para n
pequeñas. La pequeñez de n depende de muchos factores como el tiempo empleado en una
llamada recursiva la cual es una propiedad de la arquitectura de la maquina y de la estrategia
utilizada por el compilador para realizar las llamadas a procedimientos en el lenguaje en que se
escribió el método de clasificación Knuth sugiere 9 como el tamaño del subarreglos en el que
Quicksort debe llamar a un algoritmo de clasificación mas simples.
Existe otra forma de acelerar Quicksort que en realidad es una forma de canjear espacio por
tiempo la misma idea es valida para cualquier otro algoritmo de clasificación si se tiene espacio
disponibles se crea un arreglo de apuntadores a los registros de l arreglo A se efectúan las
comparaciones entre las claves de los registros apuntadores pero sin mover los registros en
vez de eso se mueven los apuntadores a los registros de la misma forma que la clasificación
rápida mueve los registro al final los apuntadores leídos de izquierda a derecha apuntan a los
registros en el orden deseado y será relativamente fácil reordenar los registros de A en el
orden correcto.
Clasificación por montículos Heapsort

En esta sección se desarrolla un algoritmo de clasificación llamado clasificación por montículos
cuyo peor caso y el caso promedio son 0(nlogn). Este algoritmo puede expresarse en forma
abstracta por medio de las cuatro operaciones de conjuntos Insertar ,Suprime ,Vacía y Min.
Los arboles 2-3 que manejan cada operación en un tiempo O(nlogn) por operación si los
conjuntos nunca crecen mas allá de n elementos si se supone que la lista L es de longitud n el
numero de operaciones realizadas será n veces INSERTA n veces SUPRIME n veces MIN y n+1
pruebas VACIA. El tiempo total consumido por el algoritmo de la figura superior es de O(nlogn)
si se emplea una estructura de datos adecuada. La estructura de datos de árbol parcialmente
ordenado que se estudio es adecuada para la realización de este algoritmo

Clasificación Rápida Quicksort

Cargado por

Copyright:

Formatos disponibles

Clasificación Rápida Quicksort

Cargado por

Información del documento

Descripción original:

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Clasificación Rápida Quicksort

Cargado por

Copyright:

Formatos disponibles

TAREA CONCEPTUAL 5

NAYERI SUSETH LEMUS ACOSTA

En un comienzo i 0 z y j =d para que la proposición anterior se siga cumpliendo ya que no

Tiempo de ejecución de la clasificación rápida

La profundidad de ri es n-i+1 para 2 <= i<=n, y la profundidad de r1 es n-1, así, la suma de la

La cual es En el peor caso la clasificación rápida requiere un tiempo proporcional a n2

Análisis del caso promedio de la clasificación rápida

Mejoras a la clasificación rápida

Clasificación por montículos Heapsort

También podría gustarte