Sea x un arreglo y n el número de elementos en arreglo que se debe ordenar. Elegir un elemento a de una posición especifica en el arreglo (por ejemplo, a puede elegirse como el primer elemento del arreglo. Suponer que los elemento de x están separados de manera que a está colocado en la posición j y se cumplen las siguientes condiciones.
1.- Cada uno de los elementos en las posiciones de 0 a j-1 es menor o igual que a.
2.- Cada uno de los elementos en las posiciones j+1 a n-1 es mayor o igual que a.
Observe que si se cumplen esas dos condiciones para una a y j particulares, a es el j-ésimo menor elemento de x, de manera que a se mantiene en su posición j cuando el arreglo está ordenado en su totalidad. Si se repite este procedimiento con los subarreglos que van de x[0] a x[j-1] y de x[j+1] a x[n-1] y con todos los subarreglos creados mediante este proceso, el resultado final será un archivo ordenado.
Ilustremos el quicksort con un ejemplo. Si un arreglo esta dado por:
x = [25 57 48 37 12 92 86 33]
y el primer elemento se coloca en su posición correcta, el arreglo resultante es:
x = [12 25 57 48 37 92 86 33]
En este punto 25 esta en su posición correcta por lo cual podemos dividir el arreglo en
x = [12] 25 [57 48 37 92 86 33]
Ahora repetimos el procedimiento con los dos subarreglos
x = 12 25 [48 37 33] 57 [92 86]
x = 12 25 33 [37 48] 57 [86] [92]
x = 12 25 33 [37 48] 57 86 92
x = 12 25 33 37 48 57 86 92
El procedimiento es entonces.
• Buscar la partición del arreglo j.
• Ordenar el subarreglo x[0] a x[j-1]
• Ordenar el subarreglo x[j+1] a x[n-1]
Su implementación en Java es:
public void quiksort(int x[],int lo,int ho)
{
int t, l=lo, h=ho, mid;
if(ho>lo)
{
mid=x[(lo+ho)/2];
while(l<h)
{
while((l<ho)&&(x[l]<mid)) ++l;
while((h>lo)&&(x[h]>mid)) --h;
if(l<=h)
{
t = x[l];
x[l] = x[h];
x[h] = t;
++l;
--h;
}
}
if(lo<h) quiksort(x,lo,h);
if(l<ho) quiksort(x,l,ho);
}
}