QuickSort для отсортированного массива

Question

Вот моя реализация кода для алгоритма QuickSort; однако он не работает для отсортированных массивов. В чем может быть проблема?

public void insertionSort(ArrayList<String> data, int firstIndex, 
    int numberToSort) { 
    if (firstIndex + numberToSort > data.size()) 
     System.out.println("Index is larger then the date size"); 
    else { 
     for (int i = 1; i < numberToSort; i++) { 
      for (int j = 0; j < i; j++) { 
       if (data.get(firstIndex + j).compareTo(
         data.get(firstIndex + i)) > 0) 
        Collections.swap(data, firstIndex + i, firstIndex + j); 
      } 
     } 
    } 
} 

@Override 
public void quickSort(ArrayList<String> data, int firstIndex, 
     int numberToSort) { 
    if (firstIndex + numberToSort > data.size()) 
     System.out.println("Index is larger then the date size"); 
    else { 
     if (numberToSort <= 16) 
      insertionSort(data, firstIndex, numberToSort); 
     else { 
      int idx = partition(data, firstIndex, numberToSort); 
      int leftSeg = idx - firstIndex; 
      int rightSeg = numberToSort - leftSeg - 1; 

      quickSort(data, firstIndex, leftSeg); 
      quickSort(data, idx + 1, rightSeg); // This is where I get an error 
     } 
    } 
} 

@Override 
public int partition(ArrayList<String> data, int firstIndex, 
     int numberToPartition) { 
    String pivot = data.get(firstIndex); 
    int TooBigNdx = firstIndex + 1; 
    int TooSmallNdx = firstIndex + numberToPartition - 1; 

    while (TooBigNdx < TooSmallNdx) { 
     while (TooBigNdx < TooSmallNdx 
       && data.get(TooBigNdx).compareTo(pivot) <= 0) 
      TooBigNdx++; 
     while (TooSmallNdx > firstIndex 
       && data.get(TooSmallNdx).compareTo(pivot) > 0) 
      TooSmallNdx--; 
     if (TooBigNdx < TooSmallNdx) 
      Collections.swap(data, TooBigNdx, TooSmallNdx); 
    } 
    if (pivot.compareTo(data.get(TooSmallNdx)) >= 0) { 
     Collections.swap(data, firstIndex, TooSmallNdx); 
     return TooSmallNdx; 
    } 
    return firstIndex; 
} 

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

Answer 1

Я попробовал этот пример с небольшими изменениями кода, чтобы упростить его запуск. Я пробовал в разных отсортированных массивах в качестве ввода, и я не видел ничего слишком очевидного. Вы, за какой вклад его не удалось?

Ваш код в online compiler IDE for java Можете ли вы попробовать изменить вход, чтобы увидеть, где он не работает?