Проблема с пониманием обработки ограждения с помощью сортировки слиянием

Fencepost (AKA Непостоянная ошибка (OBOE), также известная как OBOB (непостоянная ошибка).

Учитывая массив, я бы обычно перебирал индекс от 0 до array.length() (полуоткрытый интервал).

Я заметил, что некоторые версии сортировки слиянием требуют, чтобы среднее значение было (начало + конец)/2. И когда вы вычисляете количество элементов в процессе слияния, мы иногда ссылаемся на использование (end - start) в качестве количества элементов или (end - mid + 1). Я не в состоянии интуитивно понять это? Мне почему-то трудно это понять, и я чувствую, что меня обманывают каждый раз, когда я смотрю на любую новую реализацию.

Может ли кто-нибудь предоставить интуитивно понятный способ понять, как я могу применить / распознать проблему изгороди? Это то же самое для многомерных массивов?

public static BigInteger mergeSort(int[] integerArray, int start, int end) {
    if (start >= end) { // less than equal to is important for cases when start = end = 0
        return BigInteger.valueOf(0);
    }
    int middle = (start + end) / 2;
    BigInteger numInv1 = mergeSort(integerArray, start, middle);
    BigInteger numInv2 = mergeSort(integerArray, middle + 1, end);
    BigInteger numInv3 = runMerge(integerArray, start, middle, end);
    return numInv1.add(numInv2).add(numInv3);
}

private static BigInteger runMerge(int[] integerArray,
                                   int start, int middle, int end) {
    BigInteger numInv = BigInteger.valueOf(0);
    int n1 = middle - start + 1;
    /*
    number of elements in 1st array is middle - start + 1. why ?
    */

    int n2 = end - middle;       // number of elements in 2nd array
    /*
    number of elements in 2nd array is end - middle. why ?
    */

    int []p = new int[n1];
    int []q = new int[n2];
    int i, j, k;
    for (i = 0; i < n1 ; i++) {
        p[i] = integerArray[start + i];
    }
    for (j = 0; j < n2; j++) {
        q[j] = integerArray[middle + j + 1];
        //Why do we do +1 here? because we use 2nd array for mid+1 till end elements
    }
    i = 0;
    j = 0;
    k = start;
    while ( i < n1 && j < n2) {
        if (p[i] <= q[j]) {
            integerArray[k++] = p[i++];
        } else {
            integerArray[k++] = q[j++];
            numInv = numInv.add(BigInteger.valueOf(n1-i));
        }
    }
    while ( i < n1 ) {
        integerArray[k++] = p[i++];
    }
    while ( j < n2 ) {
        integerArray[k++] = q[j++];
    }
    return numInv;
}

1 ответ

количество элементов в первом массиве среднее - начало + 1. почему? количество элементов во втором массиве - конец - средний. Зачем?

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

int[] myIntArray = {7,4,3,5,1,12,12,11,0,2};

Он содержит 10 элементов, но индексы идут от 0 до 9. Итак, в вашем методе mergeSort(int[] integerArray, int start, int end); так должно быть myIntArray, 0, 9не myIntArray, 1, 10 ни myIntArray, 1, 9,

Итак, при условии, что мы передаем такие аргументы, как myIntArray, 0, 9, давайте посмотрим на последний (направление сворачивания) вызова mergeSort() когда у нас есть два отсортированных подмассива:

После вычисления middle = (0 + 9) / 2 = 4 мы мысленно разбили наш начальный массив на 2 массива, например:

mergeSort(integerArray, start, middle); где start = 0 и middle = 4 (включает элементы с индексами от 0 до 4 - оба включены: 1,3,4,5,7)

а также

mergeSort(integerArray, middle + 1, end); где начало = среднее + 1 = 4 + 1 = 5 и конец = 9 (содержит числа с индексами от 5 до 9 - оба включены: 0,2,11,12,12).

Вот

q[j] = integerArray[middle + j + 1];

добавив +1 мы получаем 5-й элемент. Помните, что в стеке для текущего вызова переменная середина равна 4 и это значение (4) было передано runMerge(), Значение middle + 1 пошел на один из ранее завершенных вызовов mergeSort(),

Весь процесс продолжается до тех пор, пока мы не получим массивы размера 1, которые можно считать отсортированными, а затем мы начнем объединяться - конечно, вы уже знаете это. Как видите, эти переменные - начало, середина, конец - это позиции (индексы) элементов, а не номера элементов.

Код, который вы разместили, работает нормально, если вы рассматриваете аргументы как позиции элементов, например mergeSort(myIntArray, 0, 9); а не как количество предметов. В начале это должно быть array.length() - 1 Надеюсь, поможет:)

Другие вопросы по тегам