Ошибка алгоритма Median of Medians

Question

Я реализую алгоритм select-kth, используя метод медианной медианной точки. В частности, я следую за pseudocode listed here.. Однако мой код сбой (ошибка обсуждается ниже), я вижу, почему он сбой, но я не понимаю, что я могу с этим поделать.

Ошибка

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 32017219 
at Selection.partition(Selection.java:173) 

Причина
В ссылке вики, метод select возвратит значение если left == right. Однако, когда взаимная рекурсия вызывается из оператора return из pivot, это означает, что он вернет значение (а не индекс) обратно родительскому, а родитель установит это значение как pivotIndex.

Кодекс

public static int alg5(int[] a, int left, int right, int k) { 
    if (left == right) { 
     return a[left]; 
    } 

    while (true) { 
     int pivotIndex = pivot(a, left, right);   
     pivotIndex = partition(a, left, right, pivotIndex); 

     if (k == pivotIndex) { 
      return a[k]; 
     } else if (k < pivotIndex) { 
      right = pivotIndex - 1; 
     } else { 
      left = pivotIndex + 1; 
     } 

    } 
} 

public static int pivot(int[] a, int left, int right) { 
    for (int i = left; i <= right; i = i + 5) { 
     int subRight = i + 4; 
     if (subRight > right) { 
      subRight = right; 
     } 

     int median5 = partition5(a, i, subRight); 
     swap(a, median5, (int)(Math.floor(i/5))); 
    } 

    return alg5(a, left, (int)(left + Math.ceil((right - left)/5) - 1), ((right - left)/10)); 
} 

public static int partition5(int[] a, int left, int right) { 
    Arrays.sort(a); 

    return ((a.length - 1)/2); 
} 

public static int partition(int[] a, int left, int right, int pivotIndex) { 
    int pivotValue = a[pivotIndex]; 
    a = swap(a, pivotIndex, right); 
    int storeIndex = left; 

    for (int i = left; i <= right; i++) { 
     int aOfi = a[i]; 
     if (a[i] < pivotValue) { 
      swap(a, storeIndex, i); 
      storeIndex++; 
     } 
    } 

    swap(a, right, storeIndex); 

    return storeIndex; 
} 

Я полностью понимаю, почему мой код не работает, я просто не понимаю, как это исправить, так как это выглядит именно то, что алгоритм определяет. Указатели приветствуются!

Answer 1

Есть немало ошибок:

1. pivot Метод не должен изменять массив a. Он должен просто найти стержень для будущего partition. Грязное исправление - позвонить pivot(a.clone(), left, right);. (Вы не должны этого делать, просто чтобы дать вам представление.)

2. Math.ceil((right - left)/5) - целочисленное деление. Вы должны бросить их на поплавки: Math.ceil(((float)(right - left))/5f).

3. В partition5, вы сортируете весь массив a! Вы должны просто провести сравнения, чтобы найти индекс медианной связи между a[left] и a[right].

4. В какой-то момент вы, возможно, придется right < left, поэтому первая линия alg5 вы должны написать if (left >= right)