На месте Quicksort w/Последний элемент Pivot?

Question

Я пытаюсь реализовать In-Place Quicksort, с последним элементом в качестве моего стержня. Прикрепленный ниже мой код

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, и это не точно сортировки массива. Я не уверен, почему я получаю эту ошибку.

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

Наконец, когда указатель влево/вправо тот же, мы обмениваем центральное значение с помощью нашей оси.

Это правильный способ думать об этом? И если да, то какие ошибки имеет мой код? Любая помощь будет оценена

Answer 1

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

Чтобы исправить это, добавьте еще одну проверку в этом цикле, чтобы убедиться, что у вас не было высокого и левого креста. Затем вам может понадобиться добавить некоторую дополнительную логику, чтобы обработать это как особый случай.

Answer 2

Несколько ошибок:

• Добавить left < high проверяет ваши внутренние петли. Вы должны проверять его каждый раз, когда вы изменяете влево или вправо.

• Проверить arr[high] >= pivot не arr[high] > pivot.

• swap(arr, left, pivot); неправ. Вы должны поменять местами слева, используя позиции, а не значения. Это должно быть swap(arr, left, right);.

• Вы должны проверить left < right в своем методе быстрой сортировки.

Когда вы исправить эти ошибки, код должен выглядеть следующим образом:

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; 

     while(left < high){ 
      while(left < high && arr[left] < pivot){ 
       left++; 
      } 
      while(left < high && arr[high] >= pivot){ 
       high--; 
      } 
      swap(arr,left, high); 
     } 
     swap(arr, left, right); 
     System.out.println(Arrays.toString(arr)); 
     return left; 
    } 

    public static void quickSort(int arr[], int left, int right) { 
     if(left < right) 
     { 
      int index = partition(arr, left, right); 
      quickSort(arr, left, index - 1); 
      quickSort(arr, index, right); 
     } 
    }