Median of Medians 算法错误的中位数

Question

我正在使用中位数中位数枢轴方法实施 select-kth 算法。具体来说，我正在关注 pseudocode listed here.。但是，我的代码崩溃了（下面讨论的错误），我知道它崩溃的原因，但我不明白我能做些什么。

错误

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

原因
在 wiki link 中，方法 select 将 return 一个值如果 left == right。但是，当从 pivot 的 return 语句调用相互递归时，这意味着它将 return 一个值（而不是索引）返回给父级，父级将设置该值值为 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

错误比较多：

方法pivot不应修改数组a。它应该只是为未来找到一个支点 partition。一个肮脏的修复是调用 pivot(a.clone(), left, right);。（你不应该这样做，只是为了给你一个想法。）
Math.ceil((right - left) / 5)是整数除法。您应该将它们转换为浮点数：Math.ceil(((float)(right - left)) / 5f).
在partition5中，你对整个数组a进行排序！您应该只进行比较以找到 a[left] 和 a[right] 之间的中位数 index。
在某些时候你可能有right < left，所以alg5的第一行你应该写if (left >= right)

Median of Medians 算法错误的中位数

Median of Medians algorithm error

java

algorithm

median-of-medians