Algoritmos De Ordenamiento E Implementacion En Java

Algoritmo de Ordenamiento Quicksort.

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 (porejemplo, 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 siguientescondiciones.

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.

Observeque 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 sutotalidad. 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 finalserá 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óncorrecta, 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 8633]

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