Verwirrt mit Quicksort-Algorithmus

Question

Ich bin ein Quicksort-Algorithmus implementieren und erfolgreich das Eingabearray um einen Drehpunkt partitioniert. Das Problem ist, dass ich verwirrt bin, wie man den ersten Teil und den zweiten Teil des Arrays rekursiv sortiert (d. H. Den Bereich spezifiziert), indem dasselbe Eingabearray verwendet wird. Unten ist meine Implementierung

class QuickSort { 

    int i; 
    int l = 0; 

    public void quicksort(int A[], int n) { 

     if (n == 1) { 
      return; 
     } else { 
      partition(A, 0, n); 
//----Confused as from this point 
      quicksort(A, A[i]); 

      //Recursively sort both parts of the array 
     } 
    } 

    public int partition(int A[], int l, int r) { 
     int p = A[l];//Choose pivot 
     i = l + 1; 
     //Partition around A through P 
     for (int j = i; j < r; j++) { 
      if (A[j] < p) { 
       swap(A, i, j); 
       ++i; 
      } 
     } 
     swap(A, l, i - 1); 
     return i; 
    } 

    public void swap(int A[], int i, int j) { 
     int temp = A[i]; 
     A[i] = A[j]; 
     A[j] = temp; 
    } 
    public void display(int A[]){ 
     for (int i = 0; i < A.length; i ++){ 
      System.out.print(A[i] + " "); 
     } 
    } 
} 
class QuickSortApp{ 
    public static void main(String args[]){ 
     QuickSort quick = new QuickSort(); 
     int A[] = {6,2,7,8,4,3,5}; 
     quick.quicksort(A, A.length); 
     quick.display(A); 
    } 
} 

Bitte, ich würde auch auf anderen Ineffizienzen in meinem Algorithmus korrigiert in Kenntnis gesetzt werden. Danke

Answer 1

Ändern Sie Ihre quicksort() Signatur quicksort(int[] A, int begin, int end)

Da hast du eigentlich das Innere partition() Sortierung. Was ich tun würde, ist dies:

if (end-begin <= 1) { 
    return; 
} else { 
    int pivot = partition(A, begin, end); 
    quicksort(A, begin, pivot); 
    quicksort(A, pivot, end); 
} 

Answer 2

Erstellen Sie einen Wrapper für den Quicksort-Anruf mit der Signatur, die Sie haben, die eine andere wie quicksort(A, i, j) aufruft und Ihr Anruf vom Wrapper wird quicksort(A, 0, n) sein.