2016-09-13 5 views
1

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

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

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

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

+0

IndexOutOfBoundsException довольно очевидны; вы используете слишком большой или маленький индекс (отрицательный) для рассматриваемого массива. Кроме того, просить сообщество найти все ошибки в вашем коде вне темы. – ChiefTwoPencils

+0

@ChiefTwoPencils Это то, что этот сайт _for_. Но OP должен делать больше работы, например, отправлять точную трассировку стека и пытаться отладить ее, распечатав промежуточные результаты. –

+0

@MarkoTopolnik, точно. Итак, когда вы спрашиваете «какие ошибки имеет мой код», это не по теме. Это запрос службы отладки, который этот сайт * не *. – ChiefTwoPencils

ответ

0

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

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

+0

Дополнительная проверка уменьшит производительность, особенно для почти отсортированного ввода (где неверно предсказанные ветви не доминируют), но это не представляется возможным избежать при выборе выбора. Выбор стержня из середины обычно предпочтительнее, потому что у нас есть гарантия, что проверки '>' и '<' в какой-то момент не пройдут через массив. –

1

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

  • Добавить 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); 
     } 
    } 

 Смежные вопросы

  • Нет связанных вопросов^_^