Java quickSort algorithm indexoutofbounds

Sundar 0
Viewed 40

I'm trying to implement a quickSort algorithm after learning about it.

package qsort;

public class QuickSort {
    
    public static void main(String[] args) {
        int arr[] = {10,16,8,12,15,6,3,9,5,100};
        quickSort(arr,0,(arr.length-1));
        for(int number:arr) {
            System.out.println(number);
        }
    }

    
    public static void quickSort(int[] arr, int l, int h) {
        if(l<h) {
            
            int j=partition(arr,l,h); //pivot position as j retrieved as the one sorted element
            int[] left = new int[j];
            int[] right = new int[(arr.length-j)];
            for(int index=0;index<j;index++) {
                left[index]=arr[index];
                }
            for(int index=j;index<arr.length;index++) {
                right[index-(j)]=arr[index];
            }
            
            quickSort(left,0,j);             //Sorts the first half of the array (i.e the elements before pivot
            quickSort(right,j+1,arr.length-1);            //SOrts the second half after pivot
        }
    }
    
    public static int partition(int[] arr, int l, int h) {
        
        if(arr[l]>arr[h]) {
            swap(arr[l],arr[h]);
        }
        
        
        int pivot = arr[l];
        int i=l;
        int j=h;     //i starts from the first and increments;  j starts from last and decrements
        while(i<j) {
            
            do {
                i++;
            }while(arr[i]<=pivot);          //i keeps incrementing until i points to a value greater than pivot
        
            do {
                j--;
            }while(arr[j]>pivot);               //j keeps decrementing until it finds a value less than pivot
        
            if(i<j) {
                swap(arr[i],arr[j]);
            }
        }
        swap(arr[l],arr[j]);            // swapping the first element l with the element in j so that the pivotal element can be ordered
        return j;                      //finally j points to the one sorted index where pivot should be placed
        
    }
    
    public static void swap(int a, int b){
        int temp=a;
        a=b;
        b=temp;
    }
}

And I've been clueless about IndexOutOfBoundsException and I'm not able to find out where or how it occurs. Any help would be much appreciated.

sorting java algorithm
1 Answers

There are these issues:

  • swap doesn't swap. It just swaps the values of two local variables, but has no knowledge about an array. When swap exits, those two local variables are discarded and nothing really changed. You need to pass the array reference to swap and the two indices that are involved, and then swap should change the values in that array at those two given indices.

  • left gets j values, but then a recursive call is made with h equal to j, which is an index that is out of range. The left array has j elements, so its last index is j-1, not j.

  • right gets the remaining values, but then the recursive call is made with l equal to j+1, but that has no relation to right, whose relevant values start at index 0, not at index j+1.

  • The whole idea to copy values into new arrays left and right is wrong. This is not how quicksort is supposed to work. Even if left and right would be successfully sorted, this does not have any impact on arr, which remains unsorted. So you'd have done work for nothing. Quicksort is an inplace sorting algorithm, so you should always be working with arr, not with copies of partitions of it.

Here is the correction of the relevant functions:

    public static void quickSort(int[] arr, int l, int h) {
        if(l<h) {
            int j=partition(arr,l,h);
            // Don't create new arrays here, but sort the partition in-place:
            quickSort(arr,l,j-1);
            quickSort(arr,j+1,h);
        }
    }

    public static int partition(int[] arr, int l, int h) {
        if (arr[l]>arr[h]) {
            swap(arr, l, h); // swap needs the array reference, and two indices
        }
        int pivot = arr[l];
        int i=l;
        int j=h;
        while(i<j) {
            do {
                i++;
            }while(arr[i]<=pivot);
            do {
                j--;
            }while(arr[j]>pivot);
            if(i<j) {
                swap(arr, i, j); // see above
            }
        }
        swap(arr, l, j); // see above
        return j;
    }
    
    // swap needs the array reference and the indices to perform the swap in the array
    public static void swap(int[] arr, int i, int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

I've been clueless about IndexOutOfBoundsException and I'm not able to find out where or how it occurs.

Debugging means you read the stack trace that includes this error message. It will give you the line number where it occurs (it was on the first line in partition). Then when you have identified that line, you can start to really use a debugger, setting breakpoints and inspecting variables. One of the first things you would notice, is that arr never changes: nothing gets moved in it. And so you would continue to debug and resolve one thing after the other. It is what I did with your code.

trincot0
Related