mergeSort
ли этот алгоритм mergeSort
взаимную рекурсию? Я понимаю, что mergeSort
вызывает функцию merge
и вызывает себя (mergeSort
), но поскольку merge
не вызывает mergeSort
, это не взаимная рекурсия и просто рекурсия?
function mergeSort(arr) {
// split array
...
return merge(mergSort(firstHalf), mergeSort(secondHalf));
}
function merge (array1, array2) {
// merge both arrays
...
return singleArray;
}
Правильно: это простая рекурсия. Взаимная рекурсия также называется косвенной рекурсией: A вызывает B; B называет A.
Ваш анализ в точности верен: merge
для вызова mergeSort
, тогда у вас будет взаимная рекурсия. В опубликованном коде вызов для merge
- это простая ссылка "родитель-ребенок" в дереве вызовов.
Чтобы узнать о взаимной рекурсии для сортировки слияния, это один из методов, используемых для оптимизации сортировки слияния сверху вниз, чтобы избежать шага копирования во время слияния, где направление слияния зависит от уровня рекурсии. Альтернативой этому является передача флага в качестве параметра для направления для слияния. В приведенном ниже примере код [] - это исходный массив, b [] - рабочий массив. TopDownSplitMergeAtoA возвращает с отсортированными данными в исходном массиве, а TopDownSplitMergeAtoB возвращается с отсортированными данными в рабочем массиве, а TopDownSplitMergeAtoA вызывает TopDownSplitMergeAtoB и наоборот (это взаимная рекурсия). Единственная операция копирования происходит, если размер подмассивов один для TopDownSplitMergeAtoB, и в этом случае один элемент копируется из исходного массива в рабочий массив.
void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee);
void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee);
void Merge(int a[], int b[], size_t ll, size_t rr, size_t ee);
void MergeSort(int a[], size_t n) // entry function
{
if(n < 2) // if size < 2 return
return;
int *b = new int[n];
TopDownSplitMergeAtoA(a, b, 0, n);
delete[] b;
}
void TopDownSplitMergeAtoA(int a[], int b[], size_t ll, size_t ee)
{
if((ee - ll) == 1) // if size == 1 return
return;
size_t rr = (ll + ee)>>1; // midpoint, start of right half
TopDownSplitMergeAtoB(a, b, ll, rr);
TopDownSplitMergeAtoB(a, b, rr, ee);
Merge(b, a, ll, rr, ee); // merge b to a
}
void TopDownSplitMergeAtoB(int a[], int b[], size_t ll, size_t ee)
{
if((ee - ll) == 1){ // if size == 1 copy a to b
b[ll] = a[ll];
return;
}
size_t rr = (ll + ee)>>1; // midpoint, start of right half
TopDownSplitMergeAtoA(a, b, ll, rr);
TopDownSplitMergeAtoA(a, b, rr, ee);
Merge(a, b, ll, rr, ee); // merge a to b
}
void Merge(int a[], int b[], size_t ll, size_t rr, size_t ee)
{
size_t o = ll; // b[] index
size_t l = ll; // a[] left index
size_t r = rr; // a[] right index
while(1){ // merge data
if(a[l] <= a[r]){ // if a[l] <= a[r]
b[o++] = a[l++]; // copy a[l]
if(l < rr) // if not end of left run
continue; // continue (back to while)
while(r < ee) // else copy rest of right run
b[o++] = a[r++];
break; // and return
} else { // else a[l] > a[r]
b[o++] = a[r++]; // copy a[r]
if(r < ee) // if not end of right run
continue; // continue (back to while)
while(l < rr) // else copy rest of left run
b[o++] = a[l++];
break; // and return
}
}
}