Wie kann ich meine Java-Schnellsortierung reparieren?

Question

Das Problem ist, es ist eine nie endende Rekursion. Ich weiß nicht, wie kann ich die Rekursion beenden. Das komische ist, es funktioniert, wenn ich die arraylist (mergedArray) drucke, wird es nach einer Iteration sortiert, aber die Funktion hört nie auf. Die Fehlermeldung lautet:

"bei javaapplication9.QuickSort.simple_quick_sort (QuickSort.java:40)"

Der folgende Code:

public ArrayList<Integer> simple_quick_sort(ArrayList<Integer> arr) { 
    ArrayList<Integer> mergedArray = new ArrayList<Integer>(); 
    ArrayList<Integer> left = new ArrayList<Integer>(); 
    ArrayList<Integer> right = new ArrayList<Integer>(); 
    if (arr.size() <= 1) { 
     return arr; 
    } 
    else { 
     int pivot = arr.get(0); 
     for (int i = 0; i < arr.size(); i++) { 
      if (arr.get(i) < pivot) { 
       left.add(arr.get(i)); 
      } 
      else { 
       right.add(arr.get(i)); 
      } 
     } 

    } 
    mergedArray.addAll(left); 
    mergedArray.addAll(right); 
    simple_quick_sort(mergedArray); 
    return mergedArray; 
} 

Answer 1

public ArrayList<Integer> simple_quick_sort(ArrayList<Integer> arr) { 

    if (arr.size() <= 1) { 
    return arr; 
    } 
    else { 
    ArrayList<Integer> mergedArray = new ArrayList<Integer>(); 
    ArrayList<Integer> left = new ArrayList<Integer>(); 
    ArrayList<Integer> right = new ArrayList<Integer>(); 
    int pivot = arr.get(0); 
    for (int i = 0; i < arr.size(); i++) { 
     if (arr.get(i) < pivot) { 
      left.add(arr.get(i)); 
      left = simple_quick_sort(left); 
     } 
     else { 
      right.add(arr.get(i)); 
      right = simple_quick_sort(right); 
     } 
    } 

    } 
    mergedArray.addAll(left); 
    mergedArray.addAll(right); 
} 

Natürlich Kopieren ist im Gegensatz zu der Grundidee von Quicksort, die gut ist, weil es auf dem Array arbeiten kann, um zu sortieren, diese Kopiervorgänge und Speicherzuordnungen nicht erfordern.

Answer 2

Es tut mir leid, aber Ihre gesamte Implementierung von Quicksort ist irgendwie inkorrekt. Auch die Verwendung einer Schleife innerhalb einer rekursiven Funktion negiert die Vorteile der Verwendung von Rekursion. Wenn Sie diese Schleife implementieren möchten, würde ich vorschlagen, sie in eine andere Schleife zu verschachteln, um den Code einfacher zu machen (wird nicht so effizient wie Rekursion).

Wenn Sie mit diesem Programm fortsetzen wollen, versuchen Sie die folgende Änderung vornehmen: Wenn Sie

simple_quick_sort(mergedArray); 
return mergedArray; 

schreiben Sie nicht den Rückgabewert aus der Funktion. Sie rufen nur die Funktion auf und tun nichts mit dem zurückgegebenen Wert. Es könnte weitere Dinge geben, die behoben werden müssen, bevor dieser Code funktioniert. Wenn Sie mehr über schnelle Sortierung und Rekursion erfahren möchten, habe ich diese Seite gefunden http://www.geeksforgeeks.org/quick-sort/

Ich hoffe, das hilft!