Algoritmo di partizione QuickSort

Question

Sto provando a programmare l'algoritmo di quicksort da Cormen Algorithm Textbook. Di seguito è il mio codice.

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] + " "); 
     } 
    } 
} 

Ma, quando eseguo questo codice, ottengo un output errato.

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

Qualcuno può spiegare cosa c'è che non va. Ho implementato questo codice esattamente come indicato nel libro "Introduzione agli algoritmi". Grazie.

Answer 1

No non hanno copiato direttamente :) ho qui ...

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

dovrebbe essere

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

o

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

Il libro scrive:

for j = p to r - 1 

che include r - 1. E ricorda che il libro ha matrici che iniziano a partire da 1 e non 0. Quindi generalmente gli algoritmi nel libro dovrebbero essere "copiati" con grande cura o con array che vanno da 1.

Modifica: Informazioni sull'algoritmo per un commento L'algoritmo nel libro prende l'ultimo elemento come pivot. Sarà quindi un algoritmo terribile per array già ordinati. Finirà in O (n^2), quindi nessuno dovrebbe usare questo algoritmo in produzione (a meno che tu non sappia cosa stai facendo e quale sia il tuo input) poiché gli array tendono ad essere in qualche modo ordinati. L'algoritmo di build-in di Java è più intelligente e puoi leggerlo in Javadoc

Answer 2

Se si desidera un riferimento su come implementare l'ordinamento rapido, è possibile provare a verificare il codice sorgente effettivo per Arrays.sort (*) nel jdk, che è una versione modificata di ordinamento rapido. (http://www.oracle.com/technetwork/java/javase/downloads/index.html da scaricare se non hai già src.zip nella tua installazione jdk).

Answer 3

Fornire un'altra implementazione in java. Si basa anche sullo stesso algoritmo e si prende cura anche degli elementi duplicati nella matrice.

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 
    }