ORDENAMIENTO EN JAVA QUICK SORTSAMI
Páginas: 3 (669 palabras)
Publicado: 10 de noviembre de 2015
ORDENAMIENTO EN
JAVA QUICK SORT
COMO UTILIZAR EL QUICK SORT
DESCRIPCION DEL QUICK
SORT
• Quicksort, como Mergesort, está basado en el paradigma “dividir y
conquistar”.
• Pasos:
• Dividir: elarreglo 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 llamandorecursivamente a
quicksort.
• Combinar: Como cada arreglo ya está ordenado, no serequiere trabajo
adicional.
• Algoritmo
• Quicksor(A,p,r){
if (p
Quicksort(A,p,q);Quicksort(A,q+1, r);
ESPLICACION
• 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 delextremo 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 ilo hace primero?
• Cuando estos elementos son encontrados, son
intercambiados.
• Si estos elementos no son encontrados, i terminará igual o
superior a j.
OBSERVACIONES
• Los índices i y j nuncaacceden 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 deQuicksort:
• 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) =
• Partición demejor 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)
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)...
JAVA QUICK SORT
COMO UTILIZAR EL QUICK SORT
DESCRIPCION DEL QUICK
SORT
• Quicksort, como Mergesort, está basado en el paradigma “dividir y
conquistar”.
• Pasos:
• Dividir: elarreglo 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 llamandorecursivamente a
quicksort.
• Combinar: Como cada arreglo ya está ordenado, no serequiere trabajo
adicional.
• Algoritmo
• Quicksor(A,p,r){
if (p
Quicksort(A,p,q);Quicksort(A,q+1, r);
ESPLICACION
• 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 delextremo 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 ilo hace primero?
• Cuando estos elementos son encontrados, son
intercambiados.
• Si estos elementos no son encontrados, i terminará igual o
superior a j.
OBSERVACIONES
• Los índices i y j nuncaacceden 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 deQuicksort:
• 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) =
• Partición demejor 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)
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)...
Leer documento completo
Regístrate para leer el documento completo.