Algoritmo de Ordenamiento Quicksort

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 (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í.

 

Regresar.