Quick Sort using java

Question

This program is showing errors on compilation,can someone suggest what's wrong?

The main class:

import java.util.Scanner;
public class Sortingpro {
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        System.out.println("Enter the number of elements");
        int a=input.nextInt();
        int A[]=new int[a];
        System.out.println("Enter the elements");
        for(int i=0;i<a;i++){
            A[i]=input.nextInt();
        }
        sort quick=new sort(A,a);
        quick.display(A,a);
    }
}

The sorting class:

public class sort {
    int A[],size;
    sort(int a[],int s){
        this.A=a;
        this.size=s;
        quickSort(a,1,s);
    }
    void quickSort(int a[],int p,int r){
        while(p<r){
            int q;
            q=Partition(A,p,r);
            quickSort(A,p,q-1);
            quickSort(A,q+1,r);
        }
    }

    int Partition(int a[],int p,int r)
    {
        int x=a[r];
        int i=p-1;
        for(int j=p;j<r;j++){
            if(a[j]<=x){
                i+=1;
                int temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
        int temp=a[i+1];
        a[i+1]=a[r];
        a[r]=temp;
        return i=1;
    };
    void display(int A[],int size){
        this.A=A;
        this.size=size;
        for(int i=0;i<size;i++){
            System.out.println(A);
        }
    }

}

Exception.

*****The sorting algorithm used is from CLRS.
      I am getting the following errors through Netbeans:
      Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 3
      at sortingpro.sort.Partition(sort.java:31)
      at sortingpro.sort.quickSort(sort.java:23)
      at sortingpro.sort.<init>(sort.java:17)
      at sortingpro.Sortingpro.main(Sortingpro.java:26)

      Can you please elaborate on these errors and the remedial methods to be undertaken to solve                    the problem? Also any better methods to implement this program,coding wise?

Any suggestions on the algorithm are also welcome.However i would prefer the essence of the program to be maintained.

---

Answer 1

That's the stack trace says:

You called quick sort with max size like if i entered 10 elements, you called s with 10

quickSort(a,1,s);

This in turn calls

q=Partition(A,p,r);

With r as 10, which in turn uses array[r]

Now array starts with index 0 and goes until r-1 in your case and hence you are getting ArrayIndexOutOfBound exception. So call your quicksort method with s-1 as last parameter and 0 as start index i.e.

quickSort(a,0,s-1);

Also in your recursive solution, you are using while loop which should be if. So your quick sort becomes:

void quickSort(int a[],int p,int r){
    if(p<r){
        int q;
        q=Partition(A,p,r);
        quickSort(A,p,q-1);
        quickSort(A,q+1,r);
    }
}