Quick-sort in aufsteigender Reihenfolge

Question

Ich versuche, meine Implementierung des Quicksort durch einen Tester zu übergeben; aber ich Array Index Out Of Bounds Ausnahme von -1 auf der Linie lobt

public void quickSort(ArrayList<String> data, int firstIndex, 
         int numberToSort) { 
    if (data.size() < 16) { 
     insertionSort(data, firstIndex, numberToSort); 
    } else { 
     int index = partition(data, firstIndex, numberToSort); 

     if (firstIndex < index - 1) 
      quickSort(data, firstIndex, index - 1); 
     if (numberToSort > index) 
      quickSort(data, index, numberToSort); 
    } 

} 

@Override 
public int partition(ArrayList<String> data, int firstIndex, 
        int numberToPartition) { 
    String pivot = data.get(firstIndex); 
    int left = data.indexOf(firstIndex); 
    int right = data.indexOf(numberToPartition); 

    while (left <= right) { 
     while (data.get(left).compareTo(pivot) < 0) // this is where I get the error       
      left++; 

     while (data.get(right).compareTo(pivot) > 0) 
      right--; 

     if (left <= right) { 
      temp = data.get(left); 
      Collections.swap(data, left, right); 
      data.set(right, temp); 

      left++; 
      right--; 
     } 
    } 
    return left; 
} 

Ich habe versucht, erhalte, meinen Code zu debuggen, aber es scheint, dass ich einfach nicht sehen, wie man die Fehler zu beheben. Jede Hilfe wäre willkommen.

Answer 1

Warum in der Welt machst du

int left = data.indexOf(firstIndex); 
int right = data.indexOf(numberToPartition); 

? Dabei werden die Werte firstIndex und numberToPartition unter den Elementen der List sortiert. Diese Werte sind keineswegs sicher in den Daten vorhanden, und selbst wenn, sind sie völlig zufällig. Ihre Indizes in den Daten sind nicht sinnvoll.

Für den Fall, dass eine oder beide dieser Werte ist nicht in den Daten vorhanden, indexOf() kehrt -1, die Sie dann glücklich zu List.get() passieren.

Es sieht aus wie das, was wollen Sie mehr wie

int left = firstIndex; 
int right = firstIndex + numberToPartition - 1; 

Answer 2

Stellen Sie sicher, firstIndex nicht wirklich auftreten in data ist, wenn nicht die .indexOf Methode -1 zurück, und Sie werden ein java.lang.ArrayIndexOutOfBoundsException: -1 bei int left = data.indexOf(firstIndex);