Я пытаюсь реализовать In-Place Quicksort, с последним элементом в качестве моего стержня. Прикрепленный ниже мой кодНа месте Quicksort w/Последний элемент Pivot?
public static void main(String[] args){
int[] input = {3,2,4,6,10,1,9,7,5};
quickSort(input, 0, input.length-1);
}
public static void swap(int[] array, int i, int j) {
int tmp = array[i];
array[i] = array[j];
array[j] = tmp;
}
public static int partition(int arr[], int left, int right) {
int pivot = arr[right];
int high = right-1;
while(left < high){
while(arr[left] < pivot){
left++;
}
while(arr[high] > pivot){
high--;
}
swap(arr,left, high);
left++;
high--;
}
swap(arr, left, pivot);
System.out.println(Arrays.toString(arr));
return left;
}
public static void quickSort(int arr[], int left, int right) {
int index = partition(arr, left, right);
quickSort(arr, left, index - 1);
quickSort(arr, index, right);
}
По какой-то причине, мой код дает мне исключение IndexOutOfBounds, и это не точно сортировки массива. Я не уверен, почему я получаю эту ошибку.
Если я правильно понимаю, мы должны сделать последний элемент нашей опорой. Затем мы перебираем левый указатель вправо, пока не найдем элемент, отличный от точки поворота. После этого мы делаем то же самое с правой стороны (продолжаем двигаться влево), пока не найдем элемент, меньший, чем ось поворота. Затем мы заменяем эти элементы и продолжаем делать то же самое.
Наконец, когда указатель влево/вправо тот же, мы обмениваем центральное значение с помощью нашей оси.
Это правильный способ думать об этом? И если да, то какие ошибки имеет мой код? Любая помощь будет оценена
IndexOutOfBoundsException довольно очевидны; вы используете слишком большой или маленький индекс (отрицательный) для рассматриваемого массива. Кроме того, просить сообщество найти все ошибки в вашем коде вне темы. – ChiefTwoPencils
@ChiefTwoPencils Это то, что этот сайт _for_. Но OP должен делать больше работы, например, отправлять точную трассировку стека и пытаться отладить ее, распечатав промежуточные результаты. –
@MarkoTopolnik, точно. Итак, когда вы спрашиваете «какие ошибки имеет мой код», это не по теме. Это запрос службы отладки, который этот сайт * не *. – ChiefTwoPencils