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;
      }
  }