Algoritmo de partición QuickSort

Question

Estoy tratando de programar el algoritmo de quicksort del libro de texto de algoritmo Cormen. A continuación está mi 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] + " "); 
     } 
    } 
} 

Pero obtengo un resultado incorrecto 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 

¿Alguien puede explicar lo que está mal. Implementé este código exactamente como se indica en el libro "Introducción a los algoritmos". Gracias.

Answer 1

No, no se 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++) 

El libro escribe:

for j = p to r - 1 

que incluye r - 1. Y recuerde que el libro tiene matrices que comienzan en 1 y no en 0. Por lo tanto, los algoritmos del libro deben "copiarse" con gran cuidado o con matrices que van desde 1.

Editar: Información sobre el algoritmo para un comentario El algoritmo en el libro toma el último elemento como pivote. Por lo tanto, será un algoritmo terrible para las matrices ya ordenadas. Terminará en O (n^2) por lo que nadie debería usar este algoritmo en producción (a menos que sepa lo que está haciendo y cuál es su entrada) ya que los arreglos tienden a estar algo ordenados. El algoritmo de compilación de Java es más inteligente y puede leer sobre él en Javadoc

Answer 2

Si desea obtener alguna referencia sobre cómo implementar la ordenación rápida, puede intentar verificar el código fuente real de Arrays.sort (*) en el jdk, que es una versión modificada de ordenación rápida. (http://www.oracle.com/technetwork/java/javase/downloads/index.html para descargar si aún no tiene src.zip en su instalación de jdk).

Answer 3

Proporcionando una implementación más en Java. También se basa en el mismo algoritmo y también se ocupa de los elementos duplicados en la matriz.

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 
    }