Метод QuickSort (выберите), ошибка ArrayIndex за пределами

Question

Я работаю над заданием coms и ударил огромную стену. Мы работаем с quicksort/partition.

/** 
* An implementation of the SELECT algorithm of Figure 1 of the project 
* specification. Returns the ith order statistic in the subarray 
* arr[first], ..., arr[last]. The method must run in O(n) expected time, 
* where n = (last - first + 1). 
* 
* @param arr 
* - The data to search in 
* @param first 
* - The leftmost boundary of the subarray (inclusive) 
* @param last 
* - The rightmost boundary of the subarray (inclusive) 
* @param i 
* - The requested order statistic to find 
* @return - The ith order statistic in the subarray 
* 
* @throws IllegalArgumentException 
* - If i < 1 or i > n 
*/ 
public static int select(int[] arr, int first, int last, int i) { 
    if(first == last){ 
     return first; 
    } 
    int pivot = (arr.length/2); 
    pivot = partition(arr, first, last, pivot-1); 
    if(i == pivot){ 
     return arr[i]; 
    } else if(i < pivot){ 
     return select(arr, first, pivot-1, i); 
    } else { 
     return select(arr, pivot+1, last, i); 
    } 

} 

Вышеупомянутый метод 'select', я считаю, что это реализация quicksort. Когда я запускаю его с помощью моего метода разбиения, я постоянно получаю ошибки в ArrayIndex из-за пределов, мне интересно, вызвали ли эти ошибки мои ошибки ...

Ниже представлен раздел и метод обмена I написал. Метод разбиения работает из того, что я могу сказать, я сделал int [] из 10 и запускал его несколько раз, используя разные опорные точки. Каждый раз, когда он выкидывал, аран сортировал так, как должно быть.

public static int partition(int[] arr, int first, int last, int pivot){  
    int pValue = arr[pivot]; 
    swap(arr, last, pivot); 
    int temp = first; 
    for (int i = first; i < last; i++) { 
     if(arr[i] < pValue){ 
      swap(arr, temp, i); 
      temp++; 
     } 
    } 
    swap(arr, last, temp); 
    return arr[pivot]; 
} 

public static void swap(int[] arr, int a, int b){ 
    int temp = arr[a]; 
    arr[a] = arr[b]; 
    arr[b] = temp; 
} 

Остальные задания строит прочь выбора метода, и я хлопнув меня головой в стену в течение двух дней, чтобы получить его правильно работать .... На самом деле точки, где я второй угадывая мой выбор в степени. Думаю, как второстепенный вопрос, сколько из вас, ребята, ударили по этим стенам и потеряли всякую уверенность в себе? Последние несколько заданий, с некоторой помощью, имели смысл, но теперь я здесь и просто потерял в темноте ...

PS. Извините, если я все время вспоминаю, это были грубые выходные, и вышеупомянутое было огромной болью.

Answer 1

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

1. Что произойдет, если стержень является первым или последним элементом (например, который всегда будет выполняться на массиве из 2 элементов)? Затем, когда вы выбираете на pivot + 1 или pivot - 1, как и в конце функции выбора, вы уйдете с конца массива. Или когда вы переходите на pivot - 1. Кажется, вам нужно разбить базовый случай на вашу рекурсивную функцию. Это самый вероятный преступник.

2. Вы выбираете свой стержень на основе длины всего массива, а не по длине подмассива, что от first к last вместо от 0 до arr.length. Если first и last всегда были первым и последним элементом всего массива, то я сомневаюсь, что это проблема (хотя проблема будет еще сложнее проверять).