Java Quicksort

El método de ordenación Quicksort fue desarrollado por Hoare en el año 1960.
Es el algoritmo de ordenación más rápido.
Se basa en la técnica divide y vencerás, que consiste en ir subdividiendo el array en arrays más pequeños, y ordenar éstos. Para hacer esta división, se toma un valor del array como pivote, y se mueven todos los elementos menores que este pivote a su izquierda, y los mayores a su derecha. A continuación se aplica el mismo método a cada una de las dos partes en las que queda dividido el array.
Después de elegir el pivote se realizan dos búsquedas:
Una de izquierda a derecha, buscando un elemento mayor que el pivote
Otra de derecha a izquierda, buscando un elemento menor que el pivote.
Cuando se han encontrado los dos elementos anteriores, se intercambian, y se sigue realizando la búsqueda hasta que las dos búsquedas se encuentran.
La implementación del método de ordenación Quicksort es claramente recursiva.
Suponiendo que tomamos como pivote el primer elemento, el método Java Quicksort que implementa este algoritmo de ordenación para ordenar un array de enteros se presenta a continuación. Los parámetros izq y der son el primer y último elemento del array a tratar en cada momento.
El método ordena un array A d eenteros desde la posición izq hasta la posición der. En la primera llamada recibirá los valores izq = 0, der = ELEMENTOS-1.

public static void quicksort(int A[], int izq, int der) {

  int pivote=A[izq]; // tomamos primer elemento como pivote
  int i=izq;         // i realiza la búsqueda de izquierda a derecha
  int j=der;         // j realiza la búsqueda de derecha a izquierda
  int aux;
 
  while(i < j){                          // mientras no se crucen las búsquedas                                   
     while(A[i] <= pivote && i < j) i++; // busca elemento mayor que pivote
     while(A[j] > pivote) j--;           // busca elemento menor que pivote
     if (i < j) {                        // si no se han cruzado                      
         aux= A[i];                      // los intercambia
         A[i]=A[j];
         A[j]=aux;
     }
   }
   
   A[izq]=A[j];      // se coloca el pivote en su lugar de forma que tendremos                                    
   A[j]=pivote;      // los menores a su izquierda y los mayores a su derecha
   
   if(izq < j-1)
      quicksort(A,izq,j-1);          // ordenamos subarray izquierdo
   if(j+1 < der)
      quicksort(A,j+1,der);          // ordenamos subarray derecho
   
}
De forma gráfica el proceso sería el siguiente:


















La elección del pivote determinará la eficiencia de este algoritmo ya que determina la partición del array. Si consideramos que el array está desordenado, podemos elegir el primer elemento y el algoritmo funcionaría de forma eficiente. Pero si el array está casi ordenado, elegir el primer elemento como pivote sería una mala solución ya que obtendríamos un subarray muy pequeño y otro muy grande. Por la misma razón, elegir el último elemento del array como pivote también es una mala idea. Pretendemos conseguir que el tamaño de los subarrays sea lo más parecido posible.

Una alternativa a elegir el primer elemento es elegir como pivote un elemento al azar de entre todos los del array.
Otra estrategia es calcular la mediana de los valores de la izquierda, centro y derecha del vector.
Por ejemplo para el vector: 9 8 1 6 10 2 3, se calcula la mediana de los elementos que ocupan el primer lugar, el último y el centro o sea 9 3 6. La mediana es 6 que determinaría las particiones {1 3 2} {6} {8 10 9}.
En el peor caso, cuando el pivote es el elemento menor del array el tiempo de ejecución del método Quicksort es O(n2).
En general el tiempo medio de ejecución del Quicksort es O(n log n).

45 comentarios:

  1. estimado, el programa se cae cuando mi vector tiene mas de 10000 elementos, por que pasa?

    ResponderEliminar
    Respuestas
    1. Seguramente el error que te ha dado es este:
      Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
      Cuando el vector es muy grande se necesitan hacer muchas llamadas recursivas al método para ordenarlo y con cada llamada recursiva estamos consumiendo memoria. La memoria durante la ejecución del programa la obtenemos de una zona llamada heap y cuando se agota aparece el error.

      Eliminar
    2. porque este tipo de ordenamiento es logarítmico a mayor numero mas tiempo le lleva. Debes de hacer uno que sea exponencial esos sirven para mayor numero como un bubble sort o selection sort.

      Eliminar
  2. Hola,
    Que valor tengo que dar en la llamada del metodo a las variables izq y der para que me ordone todo bien ? Lo que comentas sobre la media de los componentes del array ?

    ResponderEliminar
  3. Me respondo a mi mismo :
    si el array esta compuesto por 10 valores :
    int izq = 0;
    int der = 9;
    Y asi funciona. Gracias por el aporte.
    Muy precioso.

    ResponderEliminar
  4. Estimado como implemento el código con listas doblemente enlazadas ???
    Gracias

    ResponderEliminar
  5. Hola Disculpa la ignorancia pero como imprimo mi arreglo ordenado?

    ResponderEliminar
    Respuestas
    1. for(int i = 0;i<array.length;i++)
      System.out.println(array[i));

      Eliminar
    2. Ponlo fuera del ciclo recursivo si es lo que preguntas, porque si no te va a imprimir un montón de veces

      Eliminar
  6. Muy bueno, se parece al código de Arrays.sort de Arrays, ahora me queda mas claro el algoritmo así como los pasos de "paso de perfeccionamiento" y "paso recursivo". Lo intente hacer pero daba un paso recursivo infinito Haha, ahora ya se donde estaba el error es buen ejercicio para comprender un poco mas de recursividad. Gracias...

    ResponderEliminar
  7. Me gustaría saber como sería el algoritmo Mergesort.

    ResponderEliminar
  8. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  9. Excelente expliacación!!

    ResponderEliminar
  10. Hola, una pequeña aportación:
    Para usar el método que ha expuesto el autor con un solo parámetro, el array. Se puede sobrecargarlo de esta manera:
    public static void quicksort(int A[]) {
    quicksort(A, 0, A.length-1);
    }
    … luego en el main podrías llamarlo así:
    int [] a={4,45,1,3,5,2};
    Quicksort(a);

    ResponderEliminar
  11. 1. Determinar la solución del sgte problema a través de Java y Diagrama de Flujo usando estructuras repetitivas while, do-while.

    Diseñar un programa para mostrar en pantalla los cubos de los 10 primeros números enteros y también la suma total de ellos.
    ayudemne xfa

    ResponderEliminar
    Respuestas
    1. hola soy tu fan, draxx guapo me saludas a Gamota

      Eliminar
  12. DelegadoDavidAmaLaCoca14 de marzo de 2015, 13:00

    Genial como siempre

    ResponderEliminar
  13. y como hago para llamar a la clase "quicksort" ??

    ResponderEliminar
    Respuestas
    1. creando un metodo principal void main, y desde ahi podes invocar esa clase quicksort, dandole volores como: int iz=0, der=9;
      saludos...

      Eliminar
  14. La idea es buena.
    Hubiese inicializado izq = 0 y der = a.length.
    Por otro lado, la recursividad es una recurso caro. Con vector de gran tamaño este algoritmo se rompe. La idea seria buscar una forma iterativa.

    ResponderEliminar
  15. Codigo para cualquier vector de objetos que recibo

    public static > void ordenaquicksort(T[] Vec, int izq, int der) {

    T pivote=Vec[izq]; // tomamos primer elemento como pivote
    int i=izq; // i realiza la búsqueda de izquierda a derecha
    int j=der; // j realiza la búsqueda de derecha a izquierda
    T aux;

    while(i 0)
    j--; // busca elemento menor que pivote
    if (i<j) { // si no se han cruzado
    aux= Vec[i]; // los intercambia
    Vec[i]=Vec[j];
    Vec[j]=aux;
    }
    }
    Vec[izq]=Vec[j]; // se coloca el pivote en su lugar de forma que tendremos
    Vec[j]=pivote; // los menores a su izquierda y los mayores a su derecha
    if(izq<j-1)
    ordenaquicksort(Vec,izq,j-1); // ordenamos subarray izquierdo
    if(j+1 <der)
    ordenaquicksort(Vec,j+1,der); // ordenamos subarray derecho
    }

    ResponderEliminar
  16. Como puedo imprimir N cantidad de numeros ?

    ResponderEliminar
  17. Este comentario ha sido eliminado por el autor.

    ResponderEliminar
  18. Un aporte mas, este es para ingresarle manualmente los datos al array
    int ini=Integer.parseInt(cont3.getText());
    int fin=Integer.parseInt(cont4.getText());
    int tam = Integer.parseInt(cont2.getText());
    /*creacion del arreglo*/
    int arr[] = new int[tam];
    /*lectura del arreglo*/
    int j = 0;
    for (int i = 0 ; i < arr.length;i++)
    {
    j+=1;
    JOptionPane.showMessageDialog(null,"Inserta el numero del metodo de quick sort: " + j );
    arr[i] = Integer.parseInt(JOptionPane.showInputDialog("Ingresa el: "+" "+j+" numero : "));
    }
    quicksort(arr,ini,fin);
    }

    ResponderEliminar
  19. metodo toString para imprimir pls

    ResponderEliminar
  20. Alguien sabe como quedaría el método quicksort con hilos?

    ResponderEliminar
  21. amigo tengo una duda, como imprimo unos contadores donde imprime las comparaciones que hace y los movimientos igual

    ResponderEliminar
  22. me gustaria saber el codigo de quicksort pero en consola

    ResponderEliminar
    Respuestas
    1. public class ORDEN {
      int i, j, aux;
      public static int D = 0;
      public static int[] arre;


      public ORDEN() {
      this.i = 0;
      this.j = 0;
      this.aux = 0;
      }

      //metodo para pedir el tamaño del arreglo
      public void Limite() {
      D = Integer.parseInt(JOptionPane.showInputDialog(null, "¿cual es el limite del arreglo?"));
      if(D > 20) {
      D = Integer.parseInt(JOptionPane.showInputDialog(null, "¡ERROR!, ingrese un numero menor que 20 "));
      }
      }
      //metodo para insertar datos
      public void insertar(int n) {
      arre = new int[n];
      for (i=0; i arre[p] && p != der)) {
      der = der -1;
      }
      if(p != der) {
      aux = arre[p];
      arre[p] = arre[der];
      arre[der] = aux;
      p = der;
      while((arre[izq] < arre[p] && p != izq )) {
      izq = izq +1;
      }
      if(p != izq) {
      band = true;
      aux = arre[p];
      arre[p] = arre[izq];
      arre[izq] = aux;
      p = izq;
      }
      }
      }
      if(inicio < (p-1)) {
      QuicksortRecursivo(arre, inicio, p-1);
      }
      if((p +1) < ultimo ) {
      QuicksortRecursivo(arre, p+1, ultimo);
      }
      }

      //metodo mostrar
      public void mostrar(int [] arre) {
      for (int i = 0; i<arre.length; i++) {
      System.out.print("[" + arre[i] + "]");
      }
      System.out.println();
      }
      }
      }

      // todo lo anterior va en una clase. en otra en mi caso le e llamado menu
      import javax.swing.JOptionPane;

      public class MENU {

      public static void main(String[] args) {
      int opcion = 0;

      ORDEN orden = new ORDEN();

      do {
      try {
      opcion = Integer.parseInt(JOptionPane.showInputDialog(null, "*BIENVENIDOS AL METODO DE ORDENACION\n"
      +"1. insercion de datos al arreglo\n "
      +"2. metodo de Quick sort recursivo \n"));
      switch(opcion) {
      case 1:
      orden.Limite();
      int arre = ORDEN.D;
      orden.insertar(arre);
      System.out.println("arreglo original");
      int [] p = ORDEN.arre;
      orden.mostrar(p);
      break;
      case 2:
      System.out.println("ARREGLO ORDENADO CON EL METODO DE ORDENACION DE QUICK SORT RECURSIVO ");
      System.out.println("arreglo ordenado");
      int [] aa = ORDEN.arre;
      orden.QuicksortRecursivo(aa, 0, aa.length -1);
      orden.mostrar(aa);
      break;

      case 3:
      JOptionPane.showMessageDialog(null, "¡Finalizado!");
      break;
      default:
      JOptionPane.showMessageDialog(null, "¡Opcion incorrecta!");
      break;

      }

      }catch(NumberFormatException n) {
      JOptionPane.showMessageDialog(null, "¡Error! " + n.getMessage());
      }

      }while (opcion !=3);

      }

      }

      Eliminar
  23. A mi solo me dice que la clase public static void main(String[]args){ alguien sabe como arreglar esto
    Gracias por su atencion.

    ResponderEliminar
  24. Estoy impresionado por lo bien explicado y sencillo que hiciste este método de ordenación, muchas gracias! me sirvió muchísimo

    ResponderEliminar
  25. Disculpa mi duda seria en como se realizaria de manera descendiente seria editando la forma de impresion o cambiando directamente el codigi?

    ResponderEliminar
    Respuestas
    1. si alguien pudiera apoyarnos como realizarlo descendente, gracias

      Eliminar
    2. public static void quicksort(int A[], int izq, int der) {

      int pivote=A[izq]; // tomamos primer elemento como pivote
      int i=izq; // i realiza la búsqueda de izquierda a derecha
      int j=der; // j realiza la búsqueda de derecha a izquierda
      int aux;

      while(i < j){ // mientras no se crucen las búsquedas
      while(A[i] >= pivote && i < j) i++; // busca elemento menor que pivote
      while(A[j] < pivote) j--; // busca elemento mayor que pivote
      if (i < j) { // si no se han cruzado
      aux= A[i]; // los intercambia
      A[i]=A[j];
      A[j]=aux;
      }
      }

      A[izq]=A[j]; // se coloca el pivote en su lugar de forma que tendremos
      A[j]=pivote; // los menores a su izquierda y los mayores a su derecha

      if(izq < j-1)
      quicksort(A,izq,j-1); // ordenamos subarray izquierdo
      if(j+1 < der)
      quicksort(A,j+1,der); // ordenamos subarray derecho

      }

      Eliminar
  26. Hola me pueden ayudar con un trabajo es sobre programacion en java netbeans metodo de quicksort y shelllsort un algoritmo y un diagrama de flujo

    ResponderEliminar
  27. Hola. Cómo hago para ordenar una lista doblemente enlazada con el método QuickSort?

    ResponderEliminar
  28. Es una lista en la que tengo nombres y puntajes, y tengo que ordenar por puntaje en sentido descendente.

    ResponderEliminar