Quick Sort Java . ArrayIndexoutofBoundsException

Question

I want to quicksort algoritm.I am learning the quicksort algoritm.

Out: ArrayIndexoutofBoundsException error.I could not find the fault.

I not good English.Sorry. How do I solve this problem?

public class Quickort {
static int partition(int arr[],int left,int right){
    int i=left;
    int j=right;
    int tmp;    
    int pivot=(left/right)/2;
    while(i<=j){
        while(arr[i]<pivot)
            i++;
        while(arr[j]>pivot)
            j--;

        if(i<=j){
        tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
        i++;
        j--;
        }
     }
    return i;
}
static void quicksort(int arr[],int left,int right){
int index=partition(arr,left,right);

if(left<index-1)
    quicksort(arr, left, index-1);
if(index<right)
quicksort(arr, index, right);


}


public static void main(String[] args) {
    int [] arr={8,4,1,7,9,4,3,2,5};
    quicksort(arr,0,arr.length-1);


}

}

Answer 1

value of pivot variable should be an element from your array (int pivot = arr[right];).

Try this:

static int partition(int arr[], int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    int tmp;
    for (int j = left; j <= right; j++) {
        if (arr[j] <= pivot) {
            i++;
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
    return i;
}

static void quicksort(int arr[], int left, int right) {
    if(left < right){
        int index = partition(arr, left, right);
        quicksort(arr, left, index - 1);
        quicksort(arr, index + 1, right);
    }
}

Answer 2

According to your code

  int pivot=(left/right)/2;

You will get pivot as zero. and because of this loop

while(arr[j]>pivot)
        j--;

j becomes -1 and as array not contains this, it is throwing ArrayIndexoutofBoundsException

Answer 3

change int pivot=(left/right)/2; to int pivot=(left+right)/2;