Quicksort. How to choose pivot element?

Question

I read about quicksort algorithm and I don't understand how to choose pivot element. From tutorials I get example code of quciksort:

public void quicksort(int[] A, int left, int right) {
    int pivot = A[left + (right - left) / 2];
    int i = left;
    int j = right;
    while (i <= j) {
        while (A[i] < pivot) {
            i++;
        }
        while (A[j] > pivot) {
            j--;
        }
        if (i <= j) {
            exchange(i, j);
            i++;
            j--;
        }
    }

    if(left < j)
        quicksort(A,left,j);
    if(i < right)
        quicksort(A,i,right);
}

But why we choose pivot using this A[left + (right - left) / 2];?

Why not A[(right - left) / 2]

Answer 1

Consider left=6, right=10, then (right-left)/2 is 2. You are choosing an element which is not in the range of your sub-array?

You can choose any element between 6 and 10 as for quick sort.But if you choose first or last element and if the array is sorted, then your algorithm may go to O(n^2) running time. So it is always better to choose middle element.

Answer 2

Suppose left=3 and right=9 then right-left/2 = 3 that is not middle but its 6 that is = left + (right - left) / 2. (just added base value left).

Thanks to @Dukeling:
You can simple write (left + right) / 2.

    left + (right-left)/2 
=>  2*left/2 + (right-left)/2    //multiply (left * 2/2)
=>  (2*left + right-left)/2 
=>  (left + right)/2

Answer 3

may be you should understand this function means:quicksort the array A from index left to index right.And what is A[(right - left) / 2]?may be it is not an element of array A.

Answer 4

Left = minimum Right = maximum How do you get the middle? (Maximum - minimum) / 2

Basically it searches for the middle of the array as the pivot point.

Since the array does not start from 0, and the minimum is not a constant number, you add the minimum to the result - and that's the middle of the current array.