why ArrayIndexOutOFBoundException in bidirectional bubble sort?

Question

I could not understand why this code is giving ArrayIndexOutOfBoundsException. here is my code to implement bidirectional bubble sort.

static void bubble(int[] a){
    int temp;
    for(int i=a.length-1,k=0;i!=k;i--,k++){
        for(int j=k;j<i;j++){
            if(a[j]>a[j+1]){
            temp=a[j];
            a[j]=a[j+1];
            a[j+1]=temp;
            }
        }
        for(int j=i-1;j>k;j--){
            if(a[j-1]>a[j]){
            temp=a[j];
            a[j]=a[j-1];
            a[j-1]=temp;
            }
        }
    }
}

Step through the code in the debugger built into your IDE. Watch `i`, `k`, and `j`, in particular where they're used to access `a` (and allow for the `+1` and `-1` you're using sometimes). You'll find the bug. — T.J. Crowder, Mar 25 '17 at 09:03
@Shreya Try using an IDE to insert breakpoints and monitor the progress of the code. You should be able to see the scenario where a non-existent index is accessed. — kkaosninja, Mar 25 '17 at 09:03
Debug your code. But, as I see, if `a.length` is even, then `i` is uneven but `k` is even, so you'll never receive `i==k` situation. — Viacheslav Zhukov, Mar 25 '17 at 09:07
Possible duplicate of [What causes a java.lang.ArrayIndexOutOfBoundsException and how do I prevent it?](http://stackoverflow.com/questions/5554734/what-causes-a-java-lang-arrayindexoutofboundsexception-and-how-do-i-prevent-it) — Tom, Mar 25 '17 at 09:33

score 2 · Answer 1 · answered Mar 25 '17 at 09:07

2

I think it is because of that line:

for(int i=a.length-1,k=0;i!=k;i--,k++)

you incremnt k and decrement i, but your just checking for !=. But the difference each time is 2, so you will not neccesarily get the !=. Try to replace it by >:

for(int i=a.length-1,k=0;i>k;i--,k++){

answered Mar 25 '17 at 09:07

Markus

1,141
1
9
25

yes its working now!! thanks for your help... – Shreya Jain Mar 25 '17 at 12:30
Then please mark my answer as solution. – Markus Mar 25 '17 at 12:55

score 1 · Answer 2 · answered Mar 25 '17 at 09:09

1

if a.length is 4, then i=3, k=0.

on next iteration: i=2, k=1.

next: i=1, k=2

next: i=0, k=3, j=k, a[j+1] -> ArrayIndexOutOfBoundsException

answered Mar 25 '17 at 09:09

Pavlo Plynko

586
9
27

score 0 · Answer 3 · answered Mar 25 '17 at 09:32

Your outer for never checks for bounds:

for(int i=a.length-1,k=0;i!=k;i--,k++){

If for any reason i will never be equal with k, then your for cycle will reach i == -1 and k == a.length. If you have an odd number of elements, then when i and k reach the median, the for will stop. But what if the number of elements is pair? Like 10? When i reaches 5 and k reaches 4, then you increase k to 5 and decrease i to 4. So they will never be equal. You will need to check for i >= k instead if i!=k.

@shreyajain if this answers your question, then you might want to accept it as the correct answer. — Lajos Arpad, Mar 25 '17 at 12:51

why ArrayIndexOutOFBoundException in bidirectional bubble sort?

3 Answers3