Быстрая сортировка по возрастанию

Question

Я пытаюсь передать свою реализацию Quicksort через тестер; Однако, я получаю массив Index Out Of Bounds исключения -1 на Commended линии

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; 
} 

я пытался отладить мой код, но кажется, что я просто не вижу способ исправить ошибку. Любая помощь будет оценена по достоинству.

Answer 1

Почему в мире вы делаете

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

? Это ищет значения firstIndex и numberToPartition среди элементов List, которые сортируются. Эти ценности отнюдь не обязательно присутствуют в данных, и даже если они есть, это совершенно случайно. Их индексы в данных не имеют смысла.

В том случае, если один или оба из этих значений является не присутствуют в данных, indexOf() возвращает -1, который затем благополучно перейти к List.get().

Похоже, что вы хотите больше похож

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

Answer 2

Убедитесь firstIndex ли на самом деле происходит в data, если не метод .indexOf возвращает -1 и вы получаете java.lang.ArrayIndexOutOfBoundsException: -1 в int left = data.indexOf(firstIndex);