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.
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);
}
}
Para ver este programa corriendo haga clic aquí.