Ошибка выхода за границы с правилом Медиана медианы при использовании раздела из быстрой сортировки

Question

Я слежу за выбором k-го элемента, используя медиана медианы алгоритм из Основы алгоритмов , и у меня возникают проблемы с его реализацией в Java. Я получаю массив из-за ошибки и задаюсь вопросом, может ли кто-нибудь помочь мне правильно реализовать этот алгоритм.

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(test2.java:11)

Это значения переменных:

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

Так как мой массив начинается с размера 10, r будет 2. При повторном вызове partition2 из pivotitem значение r будет равно 0, что приведет к массиву T размера 0. Тогда low и high будут равны 0, ничего не возвращая, что где я получаю свою ошибку. Я не знаю, почему это происходит, потому что мой код похож на алгоритм в книге.

Answer 1

Оригинал С-кода?partition2 вызывается с помощью &

index& pivotpoint)

, что означает ссылку, то есть измененный результат, видимый вызывающей стороной.

Вы, кажется, обращались к этому со статической «точкой поворота», но тогда вы не можете использовать ее в качестве параметра;это будет просто скрывать статический член.

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

Это еще не завершено.

Answer 2

У меня есть некоторые другие улучшения, без решения, но, возможно, лучшая основа, чтобы пойти дальше:

• Не все переменные объявляются в начале метода (в стиле Паскаля), чтобы уменьшить их область видимости. Это облегчает рассуждения о коде.
• Я немного унифицировал порядок параметров (int[], int, ...)
• удалено из if ... return else ....
• разделить раздел 2 на 2 метода.
• добавлен метод отладки show, который запускает счетчик для остановки в бесконечном цикле.

• удалил комментарии, которые мне не помогли. Может быть, вы можете добавить лучшие комментарии.

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

Answer 3

Ваш метод обмена выглядит так, как будто он принимает индексы в качестве аргумента, но вы кормите его значениями

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

Это не причина вашей ошибки, и ошибка сохраняется после изменения вызовов, но, возможно, вы ошиблись несколько раз. Кстати: куда делся код?