Quicksort Help - Partition

Question

Ich implementiere meinen eigenen Quicksort iterativ und mit Rekursion.

Es wird die erste Partition Geldstrafe, wo Zahlen auf der rechten Seite des Pivot größer als und links kleiner als sind.

Allerdings scheint meine Partition nicht die rechte Seite und nur die linke zu partitionieren.

int[] data = {3,5,2,7,11,9,1,88,22}; 

public void qSort(int[] data, int left, int right){ 
    int pivot = partition(data,left,right); 
    pivot = partition(data,pivot,data.length-1); // Test example for right side only 
} 

public int partition(int[] data, int left, int right){ 
    int pivot = left; 
    left++; 

    while (left <= right){ 
     while ((left <= right) && (data[left] <= data[pivot])) { 
      left++; 
     } 

     while ((left <= right) && (data[right] >= data[pivot])){ 
      right--; 
     } 

     if (left < right){ 
      int temp = data[left]; 
      data[left] = data[right]; 
      data[right] = temp; 
      left++; 
      right--; 
     }   
    } 

    if (data[right] < data[pivot]){ 
     int temp = data[right]; 
     data[right] = data[pivot]; 
     data[pivot] = temp; 
     pivot = right; 
    } 

    return pivot; 
} 

Jede Hilfe wäre willkommen, ich bin :(

stapfte

Answer 1

Eigentlich Partition Implementierung funktioniert gut, übergeben Sie den falschen left Parameter partition in:

pivot = partition(data, pivot, data.length - 1); // Test example for right side only 

Es sollte :

pivot = partition(data, pivot + 1, data.length - 1); // You need to exclude the pivot itself. 

Weil in Ihrer Implementierung, Sie wählen das Element ganz links als Pivot. Wenn Sie also pivot als left Parameter übergeben, wenn Sie versuchen, den rechten Teil zu partitionieren, wird alles gleich bleiben, da es bereits partitioniert ist.