CODEWITHSUNDEEP
javaalgorithmlanguage-agnosticquicksort
WelcomeTo
WelcomeTo

Reputation: 20571

Quicksort. How to choose pivot element?

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]

Upvotes: 5

Views: 14876

Answers (6)

sainiajay
sainiajay

Reputation: 81

( 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.

Upvotes: 1

Grijesh Chauhan
Grijesh Chauhan

Reputation: 58271

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

Upvotes: 5

Adam Cohen
Adam Cohen

Reputation: 91

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.

Upvotes: 1

leiyufeng
leiyufeng

Reputation: 11

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.

Upvotes: 1

banarun
banarun

Reputation: 2321

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.

Upvotes: 11

cgledezma
cgledezma

Reputation: 622

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.

Upvotes: 0

Related Questions