Instituto Tecnolgico de Len

Omar Salas Rodrguez

Ricardo Santana Mora Montiel
Francisco Xavier Bujdud Mungua
28/10/15
 Sobre Quicksort
Su autor es C.A. Hoare, quien lo
bautizo.
Se le conoce tambin como Mtodo
Rpido
Es actualmente el mtodo de insercin
mas eficiente de los mtodos de
ordenacin interna.
Se basa en el principio de Divide y
vencers
Generalmente se usa en arreglos.
Idea Bsica del Quicksort
Se toma un elemento n que ser el primer elemento del arreglo y
empezara a compararse con la ultima posicin del arreglo.
Se ubican todos los elementos mayores a n a su derecha y los
menores e iguales a su izquierda, tratando de poner a n en su
posicin correcta.
Se repite el proces, pero ahora para los conjuntos que se encuentran
a la derecha e izquierda de n.
El proceso termina cuando los elementos se encuentran ordenados.
 Ejemplo en java
public static void quicksort(int A[], int izq, int der) { A[izq]=A[j]; // se coloca el pivote en su lugar de
forma que tendremos
int pivote=A[izq]; // tomamos primer elemento como A[j]=pivote; // los menores a su izquierda y los
pivote mayores a su derecha
int i=izq; // i realiza la bsqueda de izquierda a if(izq<j-1)
derecha quicksort(A,izq,j-1); // ordenamos subarray
int j=der; // j realiza la bsqueda de derecha a izquierdo
izquierda if(j+1 <der)
int aux; quicksort(A,j+1,der); // ordenamos subarray
while(i<j){ // mientras no se crucen las derecho
bsquedas }
while(A[i]<=pivote && i<j) i++; // busca elemento
mayor que pivote
while(A[j]>pivote) j--; // busca elemento menor
que pivote
if (i<j) { // si no se han cruzado
aux= A[i]; // los intercambia
A[i]=A[j];
A[j]=aux;
}
}