CODEWITHSUNDEEP
javaalgorithmdebuggingquicksort
seeker
seeker

Reputation: 6991

ArrayIndexOutofBoundsException in QuickSort Implementation

I'm trying out an implementation of QuickSort but getting an 

 Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at com.JavaReference.QuickSort.swap(QuickSort.java:50)
at com.JavaReference.QuickSort.randPartition(QuickSort.java:20)
at com.JavaReference.QuickSort.randSort(QuickSort.java:12)
at com.JavaReference.QuickSort.randSort(QuickSort.java:13)
at com.JavaReference.QuickSort.randSort(QuickSort.java:13)
at com.JavaReference.QuickSort.randSort(QuickSort.java:13)
at com.JavaReference.QuickSort.randSort(QuickSort.java:13)
at com.JavaReference.QuickSort.randSort(QuickSort.java:8)
at com.JavaReference.QuickSort.main(QuickSort.java:59)

Here's my source code[here.]

Im a newbie to programming so any advice on where Im going wrong would be appreciated.

EDIT:Added entire stacktrace

Upvotes: 0

Views: 451

Answers (6)

seeker
seeker

Reputation: 6991

Well folks, It was my bad earlier, Id missed a critical

 \\\Other code 
 if(left<right){
    int pivot=randPartition(a,left,right);// testing purposes

    randSort(a,left,pivot-1);........
 ...

in the randSort() function, I guess this was making right go negative .Sorry for all the noise.

Upvotes: 0

Franz
Franz

Reputation: 11

java.lang.ArrayIndexOutOfBoundsException: -1 does always tell you you're trying to call an array at an index which doesn't exist in this array. Here the value of a ( Try to do System.out.println(a) which will show you the value of a) becomes at one time of the excecution -1. So you try to call array[-1] which causes the exception because the array begins at an index of 0. you need to change your algorithm so your method swap will only be called with values int[] array, value between 0 and array.length-1, value between 0 and array.length

Upvotes: 1

joachim foobar
joachim foobar

Reputation: 51

I think it does not make sense to allow the pivot to be either left or right. This is because pivot should be used to separate two parts of the arry to be sorted (divide and conquer). To be most efficient, both parts should be equal in size.

So if left and right differ only by one, you should end recursion anyway.

Upvotes: 0

P&#233;ter T&#246;r&#246;k
P&#233;ter T&#246;r&#246;k

Reputation: 116266

My suspect is line 30:

            int i =left-1;

Since left is initially 0, i will become -1. Then on line 35 you call

                            swap(a,i,j);

and bang.

OK, from the stack trace it seems my first guess was wrong.

Second guess: from the stack trace it shows that the array is partitioned 4 times, and then at the 5th attempt the exception comes. It is thrown on line 50:

int temp= array[a];

a is the first parameter to swap. The call to swap on line 20 was

swap(a,right,randPivot);

thus right is -1 at that point. This value comes from here (line 13):

randSort(a,left,pivot-1);

If pivot is 0 at this point, shit happens. And it can become 0 since it is taken as a random value between left and right, inclusive. (And actually, that is a mistake, as for effective partitioning, pivot should fall between left and right, noninclusive.) Currently, the probability of pivot becoming 0 increases as the leftmost partition becomes smaller. You need to introduce a check for this (or, more generally, to detect array partitions of size 1, which can't be partitioned further), to stop the recursion in time.

Upvotes: 1

Marcin Wroblewski
Marcin Wroblewski

Reputation: 3571

Just a hint. This function:

public static void randSort(int a[],int left,int right)

leads to infinite recursion (it will call itself forever). At some point you will call swap with arguments left=0 and right=-1 (because randPartition returns 0 at some point).

Upvotes: 0

santoine
santoine

Reputation: 11

You are trying to access to the element of the array with the index -1. This always throws an Exception. Check that the index (a >= 0).

Upvotes: 0

Related Questions