Out of bounds error with Median of Median rule using partition from Quicksort

I am following a selection of kth element using median of median algorithm from Foundations of Algorithms and I am having trouble implementing it in java. I am getting an array out of bounds error and was wondering if someone can help me implement this algorithm correctly.

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 0
    at test2.selection2(test2.java:23)
    at test2.select4(test2.java:16)
    at test2.partition2(test2.java:55)
    at test2.selection2(test2.java:27)
    at test2.select4(test2.java:16)
    at test2.partition2(test2.java:55)
    at test2.selection2(test2.java:27)
    at test2.select4(test2.java:16)
    at test2.main(te开发者_开发知识库st2.java:11)

These are the values of the variables:

N size = 10
low = 0
high = 10
k = 3
arraysize = 10
r = 2
i = 1,2,3
first = 0,5,10
last = 4,9,11
lower = 7, 33
upper = 10, 44

-pivotitem
T size = 2
low = 0
high = 2
k = 1
arraysize = 10
r = 0

high==low [0]
list is empty

Since my array starts at size 10, r will be 2. When partition2 is called again from pivotitem, r will be 0, resulting in a array T of size 0. Then low and high will equal 0, returning nothing, which is where I am getting my error. I dont know why this is happening since my code is similar to the algorithm in the book.

Your swap method looks as if it takes indexes as argument, but you feed it with values

list = swap (list[i], list[j], list);

That's not the root of your error, and the error persists after changing the invokations, but maybe you got it multiple times wrong. BTW: Where did the code go?

The original is C-Code? partition2 is called with &

index& pivotpoint)

which means, a reference, that is, the changed result is seen by the caller.

You seemed to adress that with a static 'thepivotpoint', but then you can't use it as parameter; it will just hide the static member.

public static void partition2 (int[] list, int low, int high) // , int pivotpoint)
/* unchanged */
    thepivotpoint = j - 1;
    list = swap (mark, thepivotpoint, list);
}

It is still not complete.

I have some other improvements, without solution, but maybe a better basis to go further:

• Not all variables are declared at the head of the method (pascal-style) to reduce the scope of them. That makes it more easy to reason about the code.
• I unified the parameter order a bit (int[], int, ...)
• removed else from if ... return else ....
• splitted partition2 into 2 methods.
• added a method for debugging show which triggers a counter, to stop in an endless loop.

• removed comments which didn't helped me. Maybe you can add better comments.

  import java.util.Arrays;
  
  public class Pivot
  {
      static int thepivotpoint;
  
      public static void main(String[] args)
      {
          int[] list = {17, 10, 44, 7, 7, 33, 24, 10, 48, 49 };
          thepivotpoint = 0;
          System.out.println (select4 (list, list.length, 3));
      }
  
      public static int select4 (int[] list, int high, int k)
      {
          return selection2 (list, 0, high, k);
          // return selection2 (list, 1, high, k);
      }
  
      public static int selection2 (int[] list, int low, int high, int k)
      {
          if (high == low)
              return list[low];
          partition2 (list, low, high);
          if (k == thepivotpoint)
              return list [thepivotpoint];
          if (k < thepivotpoint)
              return selection2 (list, low, thepivotpoint - 1, k);
          return selection2 (list, thepivotpoint + 1, high, k);
      }
  
      static int count = 0;
      public static void show (int [] T)
      {
          for (int i : T)
              System.out.print (i + "\t");    
          System.out.println ();  
          if (++count > 20) System.exit (1);
      }
  
      public static void partition2 (int[] list, int low, int high) 
      {
          int arraysize = high - low;
          int r = (int) Math.ceil (arraysize / 5);
          int [] T = new int[r+1];
          for (int i = 1; i <= r; i++)
          {
              int first = low + 5 * i - 5;
              int last = Math.min (low + 5 * i - 1, arraysize);
              T [i] = median (list, first, last);
          }
          show (list);
          approximateTheMedian (T, r, low, high, list);
      }
  
      public static void approximateTheMedian (int [] T, int r, int low, int high, int [] list) 
      {
          int pivotitem = select4 (T, r, (r + 1) / 2); 
          int j = low;
          int mark = 0;
          for (int i = low; i < high; i++)
          {
              if (list[i] == pivotitem)
              {
                  list = swap (i, j, list);
                  mark = j; //mark where pivotitem placed
                  j++;
              }
              else if (list[i] < pivotitem)
              {
                  list = swap (i, j, list);
                  j++;
              }
          }
          thepivotpoint = j - 1;
          list = swap (mark, thepivotpoint, list);
      }
  
      public static int median (int[] list, int start, int end)
      {
          int [] copy = (int[]) list.clone ();
          Arrays.sort (copy);
          return copy [(start + end) / 2];
      }
  
      public static int[] swap (int one, int two, int[] list)
      {
          int dummy = list[one];
          list[one] = list[two];
          list[two] = dummy;
          return list;
      }
  }