Random pivot не работает быстрая сортировка

Question

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

• arr[left]
• arr[right - 1]
• arr[(left + right)/2]

Однако я думал, что любой элемент должен работать. Когда я меняю его на что-то вроде arr[1], код перестает работать ... Я что-то не понимаю о стержне?

Вот код для partition() метода:

public static int partition(int arr[], int left, int right) { 
    // Pick a pivot point. Can be any element. 
    int pivot = arr[(left + right)/2]; 

    while (left <= right) { 
     while (arr[left] < pivot) { 
      left++; 
     } 

     while (arr[right] > pivot) { 
      right--; 
     } 

     if (left <= right) { 
      swap(arr, left, right); 
      left++; 
      right--; 
     } 
    } 

    return left; 
} 

А вот ссылка на полный Быстрый код Сортировка: https://gist.github.com/anonymous/e1c74f2794ecb5b898ab

Как примечание стороны, я также немного неуверен почему мы возвращаем left из метода partition().

Answer 1

Сводка в Quicksort должна быть выбрана из элементов разделяемого подматрицы. Поэтому он должен быть arr[i] таким образом, что i находится между left и right. Выбор arr[1] не может работать, если left > 1 или right < 1.

Что касается возвращения left - partition выполняет замену элементов массива в диапазоне left чтобы right таким образом, что после того, как это сделано, все элементы из left (оригинального left, передаваемые методу) к left возвращаемый методом - 1 меньше, чем все элементы из left, возвращенные способом, исходному right, переданному методу. Это позволяет сделать рекурсивный вызов quicksort для каждого из двух разделов.

Метод может возвращать right вместо этого, что потребует небольшого изменения в реализации:

Вместо вызова

if (left < index - 1) { 
     quickSort(arr, left, index - 1); 
    } 

    if (index < right) { 
     quickSort(arr, index, right); 
    } 

после раздела, вы будете называть

if (left < index) { 
     quickSort(arr, left, index); 
    } 

    if (index + 1 < right) { 
     quickSort(arr, index + 1, right); 
    }