Busca en el Blog


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


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