Ошибка переполнения стека с помощью Quicksort и медианы реализации

Question

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

меня попросили изменить в Java быстрой сортировки, чтобы установить стержень как псевдо медианы 9 значений в массиве, используя формулу i * (n-1) /8

Я написал computeMedian метод, который принимает 3 целых числа, определяет высокий, и затем возвращает это значение.

Код:

public static int computeMedian(int x, int y, int z) 
    { 
     if((x >= y && x <= z) || (x >= z && x <= y)) {return x;} 
     else if((y >= x && y <= z) || (y >= z && y <= x)) {return y;} 
     else if((z >= x && z <= y) || (z >= y && z <= x)) {return z;} 
     else { return 0; } 
    } 

Затем я использовал его в моем findPivot метод, который принимает текущие array, from, to значения и использует их, чтобы построить сводную

Вот этот код:

public static int findPivot(int[] a, int from, int to) 
    { 
     if(a.length <= 7) 
     { 
      return a[(to)/2]; 
     } 
     else if(a.length > 7 && a.length <= 40) 
     { 
      return computeMedian(a[from], a[(to)/2] , a[to]); 
     } 
     else 
     { 
      int x = computeMedian(a[0 * (to)/8], a[1 * (to)/8], a[2 * (to)/8]); 
      int y = computeMedian(a[3 * (to)/8], a[4 * (to)/8], a[5 * (to)/8]); 
      int z = computeMedian(a[6 * (to)/8], a[7 * (to)/8], a[8 * (to)/8]); 
      return computeMedian(x,y,z); 
     } 
    } 

Этот метод отлично работает для сортировки любого массива, который меньше или равен размеру 40, но как только он становится больше 40, я получаю ошибку переполнения стека возвращаясь к моему методу computeMedian в части else {}. Отмечу, что return computeMedian(a[from], a[(to)/2] , a[to]); работает в разделе> 40, если я его там помещаю, но это только медиана из 3 значений, а не медиана медианы 3-х наборов.

В настоящее время это, как я findPivot подключен к методу быстрой сортировки разделов:

private static int modPartition(int[] a, int from, int to) 
    { 
     int pivot = findPivot(a, from, to); 
     int i = from - 1; 
     int j = to + 1; 
     while(i < j) 
     { 
      i++; while (a[i] < pivot) { i++; } 
      j--; while (a[j] > pivot) { j--; } 
      if (i < j) { swap(a, i, j); } 
     } 
     return j; 
    } 

Я довольно много озадачен, почему мой computeMedian метод не работает на больших наборов данных. Я попытался помещать значения i * (n-1)/8 в массив через цикл for, сортируя их и возвращая значение в середине, а также помещая значения в массив p и вызывая computeMedian(computeMedian(p[0], p[1], p[2]), computeMedian(p[3],p[4],p[5]),...etc, и я получаю одну и ту же проблему переполнения стека, но она имеет тенденцию перемещаться в разные части моего кода и вести меня по кругу.

Я могу опубликовать любые дополнительные фрагменты, если кому-то нужно, но я думаю, что моя проблема здесь прямо здесь.

Спасибо за помощь. Я все еще участвую, и я думаю, что захват этого полностью поможет мне решить проблему в будущем самостоятельно.

Вот проблемные строки из трассировки стека: Line 16: int p = modPartition(a, from, to); Линия 18 modSort(a, p+1, to); Линия 23 int pivot = findPivot(a, from, to);

Heres мой весь метод modSort также:

public static void modSort(int[]a, int from, int to) 
    { 
     if(from >= to) { return; } 
     int p = modPartition(a, from, to); 
     modSort(a, from, p); 
     modSort(a, p+1, to); 
    } 

Answer 1

Воспроизведено и исправлены

код добавляется воспроизвести ошибку ...

private static void swap(int[] a, int i, int j) { 
    int tmp = a[i]; 
    a[i] = a[j]; 
    a[j] = tmp; 
} 

public static void main(String[] args) { 
    // Generate a sample 
//  ArrayList<Integer> list = new ArrayList<>(64); 
//  for (int i = 0; i < 64; i++) list.add(i); 
//  Collections.shuffle(list); 
//  System.out.println(list); 
    int[] arr = {40, 9, 2, 62, 8, 42, 46, 23, 61, 45, 63, 48, 43, 36, 33, 32, 1, 55, 7, 17, 16, 25, 5, 26, 22, 11, 56, 38, 60, 31, 58, 29, 51, 34, 24, 54, 4, 3, 30, 20, 57, 18, 50, 44, 41, 12, 59, 6, 53, 39, 37, 35, 28, 13, 14, 15, 0, 19, 49, 52, 21, 27, 47, 10}; 

    modSort(arr, 0, arr.length-1); 

    System.out.println(Arrays.toString(arr)); 
} 

Debugging. Установка контрольной точки для StackOverFlowError (как предложено в комментариях) не работает. Поэтому я иду на регулярную точку останова на линии (начало modSort).

Для этого образца данные начинают бесконечную рекурсию по modSort с from=3;to=5. Для этого диапазона ось p = 2, которая кажется ненормальной.

Я обвиняю findPivot(a,from,to) способ. Выглядит хорошо для поиска стержня для всего a, но не для диапазона. Попытка исправить эту ошибку:

public static int findPivot(int[] a, int from, int to) { 
    final int rangeLength = to - from + 1; 
    if(rangeLength <= 7) { 
     return a[(from + to)/2]; 
    } else if(rangeLength <= 40) { // why test "a.length > 7" ? 
     return computeMedian(a[from], a[(from + to)/2] , a[to]); 
    } else { 
     final int rangeLength_8 = (to - from)/8; 
     int x = computeMedian(a[from], a[from + rangeLength_8], a[from + 2 * rangeLength_8]); 
     int y = computeMedian(a[from + 3 * rangeLength_8], a[from + 4 * rangeLength_8], a[from + 5 * rangeLength_8]); 
     int z = computeMedian(a[from + 6 * rangeLength_8], a[from + 7 * rangeLength_8], a[to]); 
     return computeMedian(x,y,z); 
    } 
} 

Тогда он отлично работает для моего примера. Я останавливаю его в этот момент (нужно немного поспать).

Я думаю, вам стоит попытаться ознакомиться с отладчиком. Я думаю, вам было бы легче понять это.

Answer 2

Теперь, когда вы фактически включал код и сообщение об ошибке для проблемы переполнения стека, мы можем вам помочь.

Из вашей трассировки стека видно, что бесконечная рекурсия , вероятно, второй вызов modSort, потому что строка 18 повторяется.

Поскольку разница между этим вызовом и входящими параметрами является вторым параметром, я бы поставил деньги на p меньше from.

Лучший способ подтвердить, что вставить хороший старомодный документ print.

public static void modSort(int[]a, int from, int to) 
{ 
    if(from >= to) { return; } 
    int p = modPartition(a, from, to); 
    System.out.println("from=" + from + ", to=" + to + ", p=" + p); 
    modSort(a, from, p); 
    modSort(a, p+1, to); 
} 

Результирующий результат должен показывать очень четкую картину того, что не так.