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

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); 

Answer 1

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

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

P.S. две мысли, которые не входят в ваш вопрос:

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

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

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

Answer 2

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

Answer 3

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

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

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