bidirectional bubble sort

Question

Here is the code for shacker sort or bidirectional bubble sort. Something is wrong. Error is

java.lang.ArrayIndexOutOfBoundsException

Can anybody help me?

public class bidirectional{

  public static void main(String[]args){

    int x[]=new int[]{12,9,4,99,120,1,3,10};
    int j;
    int n=x.length;
    int st=-1;

    while (st<n){
      st++;
      n--;
      for (j=st;j<n;j++){
        if (x[j]>x[j+1]){
          int t=x[j];
          x[j]=x[j+1];
          x[j+1]=t;
        }
      }

      for (j=n;--j>=st;){

        if (x[j]>x[j+1]){
          int t=x[j];
          x[j]=x[j+1];
          x[j+1]=t;
        }
      }
    }

    for (int k=0;k<x.length;k++){
      System.out.println(x[k]);
    }
  }
}

thanks i have got result thanks guys i have accepted all answers

Answer 1

Did java.lang.ArrayIndexOutOfBoundsException give you the line number?

Looks like your first for loop iterates to j = n-1 but reads element from index x[j+1], which will result in an attempt to read index x[n], and the exception which you see.

Your second for loop starts decrementing from j=n and will immediately cause the out of bounds exception.

You can only access the array indices in [0, N-1]. The ArrayIndexOutOfBoundsException is communicating to you that you have used an array index > N-1 or < 0.

To solve your problem with bubble sort and your code, you will change the bounds used by your for loops.

The most important concept is to realize that because you swap elements during bubble sort, the for loop is iterating over locations where you might perform a swap operation. Those locations are the boundaries between any two array elements, not the location of each element. There are N-1 boundaries between N elements. For example, there is only one (1) way to swap two (2) items. If there is only a single (1) item, then there is no way (0) to swap that.

Due to this concept, your for loops should iterate from zero (0) to N-1 and the reverse. At each comparison, you compare the element "on the left" of this interval, x[j] with the element "on the right", x[j+1]. There is no element "on the right" of element x[N-1], that is why our element stops at interval N-2.

Change the first loop to be:

for (j=st;j<n-1;j++){

and the second:

for (j=n-1;--j>=st;){

Answer 2

I'd like to post this as a comment but i cant.

 for (j=n;--j>=st;){

Can sombody explain why one should use this?

Answer 3

Here are some useful tips:

1. Read the whole error message and look at the line it tells you caused the problem.
2. Google for the ArrayIndexOutOfBoundsException
3. Don't use meaningless names; it makes it hard for you to spot logical errors.