QuickSort Java-Implementierungsproblem

Question

Ich versuche, einen QuickSort-Algorithmus als Hausaufgabe an der Universität zu implementieren, aber ich verstehe einfach nicht, wo ein Fehler in meinem Code ist. Ich nehme an, es ist ein logischer Fehler, ich glaube, ich tausche meinen Drehpunkt falsch. Ich könnte wirklich Hilfe gebrauchen, danke im Voraus. Es ist der Code:

public class QuickSort { 
    private int [] array; 

    public QuickSort(int [] array){ 
     this.array = array; 
    } 

    public void sort(){ 
     partition(0, array.length - 1); 
    } 

    public void partition(int start, int end){ 
     if (end - start < 2){ 
      return; 
     } 
     int pivot_index = end; 
     int i = start; 
     int j = end - 1; 
     while (i < j){ 
      //both elements are not in the right place 
      if(array[i] > array[pivot_index] && array[j] <= array[pivot_index]){ 
       swap(array, i, j); 
       i++; 
       j--; 
      } 
      //the element on the left is not in place 
      else if (array[i] > array[pivot_index] && array[j] > array[pivot_index]){ 
       j--; 
      } 
      //the element on the right is not in place 
      else if (array[i] < array[pivot_index] && array[j] < array[pivot_index]){ 
       i++; 
      } 
      //both elements are in place 
      else { 
       i++; 
       j--; 
      } 
     } 
     if (array[i] > array[pivot_index]){ 
      swap(array, pivot_index, i); 
      pivot_index = i; 
     } 
     partition(start, pivot_index - 1); 
     partition(pivot_index + 1, end); 
    } 

    private static void swap(int [] tab, int index1, int index2){ 
     int temp = tab[index1]; 
     tab[index1] = tab[index2]; 
     tab[index2] = temp; 
    } 
} 

Answer 1

Lösung eines

Die Idee durch das Array iteriert zu prüfen, ob das aktuelle Element kleiner ist als die letzten (die Dreh), wenn ja Swap mit dem ersten eine, die nicht ist (Index ist lastSmaller + 1).

private void partition(int start, int end) { 
    if (start >= end) { 
     return; 
    } 

    int lastSmallest = start - 1; 
    for (int i = start; i < end; i++) { 
     if (array[i] < array[end]) 
      swap(++lastSmallest, i); 
    } 

    swap(++lastSmallest, end); 
    partition(start, lastSmallest - 1); 
    partition(lastSmallest + 1, end); 
} 

Lösung zwei

Ich denke, das ist das, was Sie implementieren möchten. Iteriere durch das Array, überspringe alle Elemente an guter Stelle links und rechts. Tausche die beiden an falscher Stelle aus.

private void partition(int start, int end) { 
     if (end <= start) { 
      return; 
     } 
     int k = end; 
     int i = start; 
     int j = end - 1; 
     while (i < j) { 
      // left is in place 
      while (i < j && array[i] < array[k]) { 
       i++; 
      } 
      // right is in place 
      while (i < j && array[j] >= array[k]) { 
       j--; 
      } 

      // both are not good 
      if (i < j) { 
       // swap 
       int temp = array[i]; 
       array[i] = array[j]; 
       array[j] = temp; 

       i++; 
       j--; 
      } 
     } 

     // swap left and pivot 
     if (array[i] >= array[k]) { 
      int temp = array[i]; 
      array[i] = array[k]; 
      array[k] = temp; 
     } 
     partition(start, i - 1); 
     partition(i + 1, end); 
} 

Der Grund, warum Ihre Lösung ist nicht funktioniert, wenn Sie beide nicht an Ort und Stelle zu finden sind, können Sie sie tauschen und den Rest des Feldes partitionieren. Sie können jedoch nicht garantieren, dass das, was Sie ausgetauscht haben, nicht gegen die Regel verstößt. Daher müssen Sie zuerst alle Elemente auf beiden Seiten überspringen und dann tauschen.