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