понимание этого алгоритма слияния?

Question

понимание этого алгоритма слияния?

У меня есть следующий код

void mergesort(int size, int ar[], int temp[])
{
if(size <=1)
{
return;}
else
{
int i = 0;
int mid = size/2;

int *left = &ar[0];
int *right = &ar[mid];
int *rend = &ar[size];
int *lend = right;

mergesort(mid,left,temp);
mergesort(size-mid,right,temp);

for(i=0; i<size;i++)
{
if(left < lend && (*left < *right || right >= rend))
{
temp[i] = *left++;
}
else
{
temp[i] = *right++;
}
}
for(i = 0; i < size; i++)
{
ar[i] = temp[i];
}
}
}

Я не мог понять, как это, если заявление работает:

if(left < lend && (*left < *right || right >= rend))
{
temp[i] = *left++;
}
else
{
temp[i] = *right++;
}

Можете ли вы сказать мне, что там происходит? Почему мы должны сравнивать адреса? (оставил < одолжить и правильно> = разорвать)

Вот как функция слияния вызывается из основного

const int SIZE = 8;
int array[SIZE] = {3,6,1,-9,0,2,4,5};
int temp[SIZE];

mergesort(SIZE, array,temp);

0

algorithm c++divide-and-conquer mergesort recursion

Решение

Другие решения

Харипрасад правильно. Тогда вы делаете сравнение left < lend, вы сравниваете адреса некоторых элементов. Поскольку массив представляет собой концептуальный набор адресов, указатели могут использоваться как индексы и итераторы. И тогда вы делаете сравнение *left < *rightНапример, вы, конечно, сравниваете значения и определяете меньшее из них.

0

Есть несколько проблем с этим кодом:

int *rend = &ar[size]; — Читает за пределами массива ar
(*left < *right || right >= rend) — Я считаю, что это должно быть (right > (rend - 1) || (*left > *right)) во избежание чтения за пределами ар.

Вы можете решить это сами, пошагово пройдя код с начальным размером массива 2 или 3. Либо быстро выявляет проблемы. Я сделал это быстро в моей голове, но не тестировал с помощью отладчика. Пусть покупатель будет бдителен.

0

Источник

Accepted Answer

Чтобы выбрать вход между левой или правой последовательностями, вам нужно знать, исчерпана ли последовательность. Вы проверяете это, проверяя указатель, чтобы увидеть, находится ли он за пределами допустимого диапазона. left < lend возвращается true если левая последовательность не исчерпаны, и right >= rend возвращается true если правильная последовательность является истощены. Таким образом if будет выполняться, когда левая последовательность не исчерпана, а либо левая позиция меньше правой, либо правая последовательность исчерпана.

Если бы вы следовали стандартным соглашениям об итераторах библиотеки, вы бы никогда не проверяли < или же > в сравнении. left != lend а также right == rend будет работать так же хорошо в коде, который вы опубликовали.

Постскриптум две мысли, которые не являются частью вашего вопроса:

Как отмечено в комментариях, в сравнении скрывается неопределенное поведение. Вам нужно проверить, исчерпана ли правая сторона до проверка значения в правой части указателя.
Сортировка слиянием естественно стабильна, если вы используете правильное сравнение. Вы хотите, чтобы любые связи были взяты из левой последовательности. В вашем случае сортировка ints это не имеет значения, так как вы не можете сказать одно и то же int от другого, но если бы это был просто ключ к части большей структуры, это могло бы иметь большое значение. Это просто вопрос замены < с <=,

Взяв все вышеперечисленные предложения вместе, вы получите:

if (left != lend && (right == rend || *left <= *right))

1