StackOverflowError при реализации QuickSort

Question

Я пытаюсь реализовать алгоритм QuickSort на ArrayList. Тем не менее, я получаю

Exception in thread "main" java.lang.StackOverflowError 
    at sorting.QuickSort.quickSort(QuickSort.java:25) 
    at sorting.QuickSort.quickSort(QuickSort.java:36) 
    at sorting.QuickSort.quickSort(QuickSort.java:36) 
    at sorting.QuickSort.quickSort(QuickSort.java:36) 
    at sorting.QuickSort.quickSort(QuickSort.java:36) 
    ... 

Я не уверен, почему происходит переполнение. Ниже моя реализация:

public static void quickSort(ArrayList<Integer> al, int fromIdx, int toIdx) { 
    int pivot, pivotIdx; 

    if (fromIdx < toIdx) { 
     pivot = al.get(fromIdx); 
     pivotIdx = fromIdx; 

     for (int i = 0; i != (fromIdx + 1); i++) { 
      if (al.get(i) <= pivot) { 
       pivotIdx += 1; 
       swap(al, pivotIdx, i); 
      } 
     } 

     swap(al, fromIdx, pivotIdx); 
     quickSort(al, fromIdx, pivotIdx - 1); 
     quickSort(al, pivotIdx + 1, toIdx); 
    } 
} 

public static void swap(ArrayList<Integer> al, int xIdx, int yIdx) { 
    Integer temp = al.get(xIdx); 
    al.set(xIdx, al.get(yIdx)); 
    al.set(yIdx, temp); 
} 

Answer 1

Если вы пытаетесь сортировать кусок массива от fromIdx к toIdx, вы никогда не должны смотреть на элемент 0, если он не находится в этом фрагменте. Но ваша реализация делает.

Ваш индексный трюк посередине также является разновидностью ... .dd. Я настоятельно рекомендую вам выполнять вырезание маленьких кусочков бумаги для массива и записывать информацию отслеживания на листе бумаги, чтобы вы могли проследить алгоритм. Если, когда вы физически это делаете, вы видите, что это не имеет смысла, тогда это тоже не имеет смысла в компьютере. И акт хранения физических кусков бумаги может показаться глупым, но очень помогает в визуализации того, что вы делаете. (Точнее, вы можете визуализировать то, что делает ваш код на самом деле, тем более вероятно, что вы сможете выяснить, не делает ли он что-то не так.)