algoritmo de partición QuickSort

Question

Estoy intentando programar el algoritmo de clasificación rápida de Cormen Algoritmo de libros de texto. A continuación se muestra el código.

class Quicksort
{
    public void qSort(int[] a, int p, int r)
    {
        if(p<r)
        {
            int q = Partition(a, p,r);
            qSort(a, p, q-1);
            qSort(a, q+1, r);
        }
     }

     private int Partition(int[] a, int p, int r)
     {
         int x = a[r];

         int i = p-1;
         int temp=0;

         for(int j=p; j<r-1; j++)
         {
             if(a[j]<=x)
             {
                 i++;
                 temp = a[i];
                 a[i] = a[j];
                 a[j] = temp;
             }
         }

         temp = a[i+1];
         a[i+1] = a[r];
         a[r] = temp;
         return (i+1);
     }
}

public class QuickSortTest
{
     public static void main(String[] args)
     {
         Quicksort qsort = new Quicksort();
         int[] array = {5, 4, 7, 2, 1, 9, 3, 6, 10, 8};

         System.out.print("Original  Array : ");
         for(int i=0; i<array.length;i++)
         {
             System.out.print(array[i] + " ");
         }

         int length = array.length;

         qsort.qSort(array, 0, length-1);

         System.out.print("Sorted  Array : ");
         for(int i=0; i<array.length;i++)
         {
             System.out.print(array[i] + " ");
         }
     }
}

Sin embargo, estoy consiguiendo una salida incorrecta cuando ejecuto este código.

Original  Array : 5 4 7 2 1 9 3 6 10 8 
Sorted  Array : 1 4 5 2 6 7 3 8 9 10 

Puede alguien por favor explique lo que está mal. He implementado el código exactamente como se indica en "Introducción a los algoritmos" libro. Gracias.

Answer 1

No, no han copiado directamente :) tengo aquí ...

for(int j=p; j<r-1; j++)

debería ser

for(int j=p; j<r; j++)

o

for(int j=p; j <= r-1; j++)

Las escrituras en el libro:

for j = p to r - 1

que incluye r - 1. Y recuerda que el libro tiene matrices, que es a partir de 1 y no 0. Así que en general, los algoritmos en el libro deben ser "copiados" con mucho cuidado o con matrices que va de 1.

Editar: Información sobre el algoritmo para un comentario El algoritmo en el libro lleva al último elemento como pivote. Por lo tanto, hará que sea un terrible algoritmo para matrices ya ordenados. Se va a terminar en O (n ^ 2), de modo que nadie debe utilizar este algoritmo en la producción (a menos que sepa lo que está haciendo y lo que su entrada es) como matrices tienden a ser algo ordenadas. construir-en Java algoritmo es más inteligente y se puede leer sobre él en el Javadoc

Answer 2

Si desea alguna referencia sobre cómo implementar rápida tipo, podría intentar comprobar el código fuente real de Arrays.sort (*) en el JDK, que es una versión modificada del tipo rápido. ( http://www.oracle.com/technetwork/java/javase /downloads/index.html de descarga si no tiene ya src.zip en la instalación de JDK).

Answer 3

Proporcionar una mayor aplicación en Java. También se basa en el mismo algoritmo y se encarga de elementos duplicados en la matriz también.

    public void sort( int[] inputArray, int lo, int high){
          int pivotIndex = partition(inputArray,lo,high);
         System. out .println("Got PivotIndex as " + pivotIndex);
          if (lo < pivotIndex -1)
                sort(inputArray,lo,pivotIndex - 1);
          if (pivotIndex+1 < high)
                sort(inputArray,pivotIndex+1,high);
          return ;
    }

    private int partition( int[] inputArray, int leftPtr,int rightPtr)
   {
         printArray(inputArray);
          int pivot = inputArray[leftPtr];
          while (leftPtr<rightPtr){
                 while (inputArray[leftPtr]<pivot)
                       leftPtr++;
                 while (inputArray[rightPtr]>pivot)
                       rightPtr--;
                 if (leftPtr<rightPtr)
                {
                       exchange(inputArray,leftPtr,rightPtr);

                          //Cases which have repeated numbers...
                        if (inputArray[leftPtr] == inputArray[rightPtr])
                             leftPtr++;
                }
         }
          return leftPtr;//return any one
   }