Проблема с пониманием обработки ограждения с помощью сортировки слиянием
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
Надеюсь, поможет:)