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.

Answer 5

( left + right ) / 2

may cause error due to overflow.

Suppose left = 1 & right = INT_MAX then ( left + right ) / 2 = 0, which is incorrect. This is caused due to overflow and to avoid this we choose left + (right - left) / 2. Mathematically both expressions are correct to choose the middle element.

Answer 6

Actually the selection of a pivot element is one of the most important parts of quicksort. An optimal selection usually depends on the structure of the arrays that you are receiving, and in general it is very hard to find a position for the pivot that suits every array.

In this particular example the tutorial is choosing as pivot the element in the middle of the segment being ordered, but probably there is no particular reason for doing so.

Me, I usually choose the last element of the segment pivot = A[right], only to avoid errors in arithmetics.