Алгоритм Медиана Медиан не работает последовательно

Question

Я реализовал алгоритм выбора / медианы медиан, используя в качестве ссылки следующее: http://www.ics.uci.edu/~eppstein/161/960130.html (здесь ранее была указана Медиана медиан в Java).

Кажется, мой код работает для небольших массивов (~100) и даже работает для массивов размером 100001 http://pastebin.com/mwRc4Hig (ответ 5008), но затем не работает на входном массиве размером 10001 http://pastebin.com/YwVBmgDk (ответ 4960, мой код выводит 4958).

Обратите внимание, что правильные ответы для приведенных выше текстов эквивалентны сортировке массива и возвращению элемента в массиве [array.length / 2], независимо от того, является ли размер массива четным или нечетным.

Я не уверен, как отладить эту проблему. Функциональность кажется произвольной, и я просто потерян. Здесь ниже мой код:

public class MedianOfMedians {

public static void main(String[] args) {
    MedianOfMedians mds = new MedianOfMedians();
    mds.run();
}

private void run() {
    Scanner in = new Scanner(System.in);
    int n = in.nextInt();
    int[] numArray = new int[n];
    for (int i = 0; i < n; i++) {
        numArray[i] = in.nextInt();
    }
    int median = select(numArray, numArray.length / 2);
    System.out.print(median);
}

private int select(int[] numArray, int k) {
    if (numArray.length <= 10) {
        int[] sorted = insertionSort(numArray);
        return sorted[k];
    }

    int divCount = (numArray.length % 5 == 0) ? numArray.length / 5 - 1 : numArray.length / 5;
    int[] medOfMed = new int[divCount + 1];
    int counter = 0;
    int[] subArray;

    while (counter <= divCount) {
        subArray = splitByFive(counter, divCount, numArray);
        medOfMed[counter] = select(subArray, subArray.length / 2);
        counter++;
    }

    int M = select(medOfMed, numArray.length / 10);

    List<Integer> lt = new ArrayList<>();
    List<Integer> eq = new ArrayList<>();
    List<Integer> gt = new ArrayList<>();
    for (int i : numArray) {
        if (i < M) {
            lt.add(i);
        } else if (i == M) {
            eq.add(i);
        } else {
            gt.add(i);
        }
    }
    if (k < lt.size()) {
        return select(createArray(lt), k);
    } else if (k > lt.size() + eq.size()) {
        return select(createArray(gt), k - lt.size() - eq.size());
    } else {
        return M;
    }
}

private int[] splitByFive(int splitIter, int divisions, int[] toSplit) {
    int numToCopy;
    if (splitIter == divisions) {
        numToCopy = toSplit.length - (5 * splitIter);
    } else {
        numToCopy = 5;
    }
    int[] subArray = new int[numToCopy];
    System.arraycopy(toSplit, splitIter * 5, subArray, 0, numToCopy);
    return subArray;
}

private int[] createArray(List<Integer> list) {
    int[] result = new int[list.size()];
    for (int i = 0; i < list.size(); i++) {
        result[i] = list.get(i);
    }
    return result;
}

private int[] insertionSort(int[] numArray) {
    for (int i = 1; i < numArray.length; i++) {
        int j = i;
        while (j - 1 >= 0 && numArray[j] < numArray[j - 1]) {
            int temp = numArray[j];
            numArray[j] = numArray[j - 1];
            numArray[j - 1] = temp;
            j--;
        }
    }
    return numArray;
}
}

Answer 1

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

Если есть вход, на котором алгоритм терпит неудачу (и, как вы обнаружили, есть), то такой вход будет наименьшим - и чем меньше этот вход, тем легче будет понять, что происходит не так. Поскольку алгоритм рекурсивный, у вас есть хороший способ изолировать первое место, где что-то идет не так: вы можете проверить, что результат, который вы собираетесь вернуть select() является правильным (использование медленного, надежного метода, такого как копирование данных во временный буфер, сортировка и последующий захват промежуточного элемента) непосредственно перед возвратом значения. Делать это будет намного проще, если вы переставите функцию, чтобы использовать только один return утверждение, например:

private int select(int[] numArray, int k) {
    int knownCorrectAnswer = selectSlowlyButDefinitelyCorrectly(numArray, k);
    int willReturn;
    if (numArray.length <= 10) {
        int[] sorted = insertionSort(numArray);
        willReturn = sorted[k];    // Just remember what we will return
    } else {    // Need to add else branch here now

        ...

        if (k < lt.size()) {
            willReturn = select(createArray(lt), k);
        } else if (k > lt.size() + eq.size()) {
            willReturn = select(createArray(gt), k - lt.size() - eq.size());
        } else {
            willReturn = M;
        }
    }    // End of inserted else branch

    if (willReturn == knownCorrectAnswer) {
        return willReturn;
    } else {
        yell("First problem occurs with numArray=<...> and k=<...>!");
    }
}

yell() должен распечатать весь экземпляр проблемы и остановить программу (например, с помощью исключения). Приятно то, что вы знаете, что когда yell() вызывается, каждый звонок select() что уже завершено было правильно - так как если это не так, yell() был бы уже вызван, и программа была бы остановлена ​​до сих пор. Таким образом, выход произведен yell() гарантированно будет первой (не обязательно самой маленькой, но часто также) подзадачей, в которой что-то пошло не так.