Metodo 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.

• 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);

    }

  }

Ejemplo Hecho por La Mestra:

package quicksort;

public class Ordenador {

  public int[] quicksort(int numeros[])

   {

    return quicksort(numeros,0,numeros.length-1);

   }

    public int[] quicksort(int numeros[],int izq,int der)

   //se crea el arreglo a manejar

  {

   if(izq>=der)

  //compara que el valor d izquierda sea mayor al de derecha y regresa el valor

  //de numeros

   return numeros;

   int i=izq,d=der; 

   //compara que el valor d la variable "i" sea diferente de "d"

  

 if(izq!=der)

        {

        int pivote;

        int aux;

        pivote = izq; //aqui se le asgina el valor de izqueirda al pivite

        while(izq!=der)

        // se realiza la comparacion, para luego imprimir los nuevos resultados

        {

        imprimeArreglo(numeros);

         while(numeros[der]>=numeros[pivote] && izq<der)

      // comparacion en la que los numeros de derecha sean mayores o iguales

      //a pivote y que sea izquerda menor a derecha

               der--;//decrementa derecha

        while(numeros[izq]<numeros[pivote] && izq<der)

   //casi misma comapracion pero inverza, ahora con izqueirda que sea menor

   //al pivote

               izq++;//incrementa izqueirda

         if(der!=izq)

         {

             aux = numeros[der];

            numeros[der]= numeros[izq];

//se le asginan los valores de derecha a los numeros izqueirda

            numeros[izq]=aux;}

// y los de izquierda toma el valor de aux q es igual a los de derecha

        }

        if(izq==der){ // se comparan si los valores son iguales

            quicksort(numeros,i,izq-1);//

            quicksort(numeros,izq+1,d);//

        }

        }

        else

            return numeros;  //regresa los numeros de cada uno

       return numeros;

    }

    public void imprimeArreglo(int arreglo[])

    {

        String imp="";

        for(int i=0;i<arreglo.length;i++)

// que i sea menor al tamaño del arreglo

        {

            if(i!=arreglo.length-1) //que i sea diferente

            imp=imp+arreglo[i]+",";

// imprime el arreglo que tomara la variable "i" q kontendra los numeros

            else

                imp=imp+arreglo[i]+"";

        }

        System.out.println(imp);

    }

    public static void main(String[] args) {

        int array[] ={4,2,5,7,6,1,3};

//valores estaticos asignados que seran ordenados del cual el 4 sera el pivote,

//que es valor que esta a la izquierda

Ordenador a = new Ordenador();

a.quicksort(array);

//los valores del arreglo pasan por el metodo quicksort

//el cual contiene las comparaciones a realizar para poder ordenarlos y obtener

//un nuevo orden.

//

    }//es un metodo que mejor funcionar debido a su eficiencia

}

Video de Quicksort...