Понимание рекурсии объединения

Большинство реализаций mergesort, которые я вижу, похожи на это. ввод в книгу алгоритмов вместе с онлайн-имплантациями, которые я ищу. Мои рекурсивные отбивные не идут намного дальше, чем возиться с поколением Фибоначчи (что было достаточно просто), так что, возможно, это несколько рекурсий, дующих мне на ум, но я не могу даже пройти через код и понять, что происходит, даже до того, функция слияния.

Как это проходит через это? Есть ли какая-то стратегия или чтение, которые я должен пройти, чтобы лучше понять этот процесс здесь?

void mergesort(int *a, int*b, int low, int high)
{
    int pivot;
    if(low<high)
    {
        pivot=(low+high)/2;
        mergesort(a,b,low,pivot);
        mergesort(a,b,pivot+1,high);
        merge(a,b,low,pivot,high);
    }
}

и слияние (хотя, откровенно говоря, я мысленно застреваю до того, как я доберусь до этой части)

void merge(int *a, int *b, int low, int pivot, int high)
{
    int h,i,j,k;
    h=low;
    i=low;
    j=pivot+1;

    while((h<=pivot)&&(j<=high))
    {
        if(a[h]<=a[j])
        {
            b[i]=a[h];
            h++;
        }
        else
        {
            b[i]=a[j];
            j++;
        }
        i++;
    }
    if(h>pivot)
    {
        for(k=j; k<=high; k++)
        {
            b[i]=a[k];
            i++;
        }
    }
    else
    {
        for(k=h; k<=pivot; k++)
        {
            b[i]=a[k];
            i++;
        }
    }
    for(k=low; k<=high; k++) a[k]=b[k];
}

Ответ 1

Я думаю, что имя функции сортировки в MergeSort является немного неправильным, его действительно следует называть "делить".

Вот визуализация алгоритма в процессе.

Каждый раз, когда функция рекурсивно, она работает с меньшим и меньшим подразделением входного массива, начиная с левой половины. Каждый раз, когда функция возвращается из рекурсии, она будет продолжена и либо начнет работать в правой половине, либо повторится снова и будет работать в большей половине.

Подобно этому

[************************]mergesort
[************]mergesort(lo,mid)
[******]mergesort(lo,mid)
[***]mergesort(lo,mid)
[**]mergesort(lo,mid)
 [**]mergesort(mid+1,hi)
[***]merge
   [***]mergesort(mid+1,hi)
   [**]mergesort*(lo,mid)
    [**]mergesort(mid+1,hi)
   [***]merge
[******]merge
      [******]mergesort(mid+1,hi)
      [***]mergesort(lo,mid)
      [**]mergesort(lo,mid)
       [**]mergesort(mid+1,hi)
      [***]merge
         [***]mergesort(mid+1,hi)
         [**]mergesort(lo,mid)
           [**]mergesort(mid+1,hi)
         [***]merge
      [******]merge
[************]merge
            [************]mergesort(mid+1,hi)
            [******]mergesort(lo,mid)
            [***]mergesort(lo,mid)
            [**]mergesort(lo,mid)
             [**]mergesort(mid+1,hi)
            [***]merge
               [***]mergesort(mid+1,hi)
               [**]mergesort(lo,mid)
                 [**]mergesort(mid+1,hi)
               [***]merge
            [******]merge
                  [******]mergesort(mid+1,hi)
                  [***]mergesort(lo,mid)
                  [**]mergesort*(lo,mid)
                    [**]mergesort(mid+1,hi)
                  [***]merge
                     [***]mergesort(mid+1,hi)    
                     [**]mergesort(lo,mid)
                      [**]mergesort(mid+1,hi)
                     [***]merge
                  [******]merge
            [************]merge
[************************]merge

Ответ 2

MERGE SORT:

1) Разделить массив пополам
2) Сортировка левой половины
3) Сортировка правой половины
4) Объедините две половины вместе

Ответ 3

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

Ваш вопрос немного неоднозначен, потому что вы не объясняете, что вы считаете запутанным, но похоже, что вы пытаетесь развернуть рекурсивные вызовы в вашей голове. Что может быть или не быть хорошо, но я думаю, что это может легко привести к тому, что у вас слишком много в голове. Вместо того, чтобы пытаться отследить код от начала до конца, посмотрите, можете ли вы концептуально понять концепцию. Сортировка слияния:

Разделение массива пополам
Сортирует левую половину
Сортирует правую половину
Объединяет две половины вместе

(1) должен быть достаточно очевидным и интуитивным для вас. Для шага (2) ключевое понимание - это, левая половина массива... представляет собой массив. Предполагая, что ваша сортировка слияния работает, она должна иметь возможность сортировать левую половину массива. Правильно? Шаг (4) на самом деле является довольно интуитивной частью алгоритма. Пример должен сделать его тривиальным:

at the start
left: [1, 3, 5], right: [2, 4, 6, 7], out: []

after step 1
left: [3, 5], right: [2, 4, 6, 7], out: [1]

after step 2
left: [3, 5], right: [4, 6, 7], out: [1, 2]

after step 3
left: [5], right: [4, 6, 7], out: [1, 2, 3]

after step 4
left: [5], right: [6, 7], out: [1, 2, 3, 4]

after step 5
left: [], right: [6, 7], out: [1, 2, 3, 4, 5]

after step 6
left: [], right: [7], out: [1, 2, 3, 4, 5, 6]

at the end
left: [], right: [], out: [1, 2, 3, 4, 5, 6, 7]

Итак, предполагая, что вы понимаете (1) и (4), можно было бы подумать о способе сортировки слияния. Представьте, что кто-то написал mergesort(), и вы уверены, что он работает. Затем вы можете использовать эту реализацию mergesort() для записи:

sort(myArray)
{
    leftHalf = myArray.subArray(0, myArray.Length/2);
    rightHalf = myArray.subArray(myArray.Length/2 + 1, myArray.Length - 1);

    sortedLeftHalf = mergesort(leftHalf);
    sortedRightHalf = mergesort(rightHalf);

    sortedArray = merge(sortedLeftHalf, sortedRightHalf);
}

Обратите внимание, что sort не использует рекурсию. Он просто говорит: "Сортируйте обе половины, а затем объедините их". Если вы поняли пример слияния, то, надеюсь, вы видите интуитивно, что эта функция sort, похоже, делает то, что она говорит... sort.

Теперь, если вы посмотрите на него более тщательно... sort() выглядит примерно так же, как mergesort()! Это потому, что это mergesort() (за исключением того, что у него нет базовых случаев, потому что он не рекурсивный!).

Но как мне нравится думать о рекурсивных функциях, предположим, что функция работает, когда вы ее вызываете. Рассматривайте это как черный ящик, который делает то, в чем вы нуждаетесь. Когда вы делаете это предположение, выяснить, как заполнить этот черный ящик, часто бывает легко. Для данного входа вы можете разбить его на более мелкие входы для подачи на черный ящик? После того, как вы решите это, осталось только обработать базовые случаи в начале вашей функции (в тех случаях, когда вам не нужно делать какие-либо рекурсивные вызовы. Например, mergesort([]) просто возвращает пустой массив; он не рекурсивный вызов mergesort()).

Наконец, это немного абстрактно, но хороший способ понять рекурсию - это на самом деле написать математические доказательства с использованием индукции. Та же стратегия, что и для написания доказательства по индукции, используется для записи рекурсивной функции:

Математическое доказательство:

Показать утверждение верно для базовых случаев
Предположим, что это верно для входов, меньших, чем некоторые n
Используйте это предположение, чтобы показать, что оно по-прежнему верно для ввода размера n

Рекурсивная функция:

Обрабатывать базовые случаи
Предположим, что ваша рекурсивная функция работает на входах, меньших, чем некоторые n
Используйте это предположение для обработки ввода размера n

Ответ 4

Что касается рекурсивной части сортировки слиянием, я нашел эту страницу очень полезной. Вы можете следить за кодом по мере его выполнения. Он показывает вам, что выполняется первым, а что следующим.

Том

Ответ 5

the mergesort() просто делит массив на две половины до тех пор, пока условие if не будет выполнено с ошибкой low < high. Поскольку вы вызываете mergesort() дважды: один с low до pivot, а второй с pivot+1 до high, это еще больше разделит вспомогательные массивы.

Давайте возьмем пример:

a[] = {9,7,2,5,6,3,4}
pivot = 0+6/2 (which will be 3)
=> first mergesort will recurse with array {9,7,2} : Left Array
=> second will pass the array {5,6,3,4} : Right Array

Он будет повторяться до тех пор, пока у вас не будет 1 элемент в каждом left, а также в массиве right. В итоге у вас будет что-то похожее:

L : {9} {7} {2} R : {5} {6} {3} {4} (each L and R will have further sub L and R)
=> which on call to merge will become

L(L{7,9} R{2}) : R(L{5,6} R{3,4})
As you can see that each sub array are getting sorted in the merge function.

=> on next call to merge the next L and R sub arrays will get in order
L{2,7,9} : R{3,4,5,6}

Now both L and R sub array are sorted within
On last call to merge they'll be merged in order

Final Array would be sorted => {2,3,4,5,6,7,9}

См. шаги слияния в ответе @roliu

Ответ 6

Извиняюсь, если на это был дан ответ. Я признаю, что это всего лишь эскиз, а не глубокое объяснение.

Хотя неясно, как выглядит фактический код с рекурсией, я смог понять рекурсию в общем смысле таким образом.

В качестве примера возьмите пример unsorted set {2,9,7,5}. Алгоритм merge_sort для краткости ниже обозначается символом ms. Затем мы можем набросать операцию как:

Шаг 1: мс (мс (мс (2), мс (9)), мс (мс (7), мс (5)))

Шаг 2: ms (ms ({2}, {9}), ms ({7}, {5}))

Шаг 3: ms ({2,9}, {5,7})

Шаг 4: {2,5,7,9}

Важно отметить, что merge_sort синглета (например, {2}) - это просто синглет (ms (2) = {2}), так что на самом глубоком уровне рекурсии мы получаем наш первый ответ. Остальные ответы затем падают как домино, когда внутренние рекурсии заканчиваются и сливаются вместе.

Часть гения алгоритма заключается в том, как он автоматически создает рекурсивную формулу шага 1 через свою конструкцию. То, что помогло мне, состояло в том, чтобы подумать о том, как сделать шаг 1 выше от статической формулы до общей рекурсии.

Ответ 7

процесс, чтобы разделить проблему на подзадачи Данный пример поможет вам понять рекурсию. int A [] = {число элементов, которые должны быть закорочены.}, int p = 0; (индекс любовника). int r = A.length - 1; (более высокий индекс).

class DivideConqure1 {
void devide(int A[], int p, int r) {
    if (p < r) {
        int q = (p + r) / 2; // divide problem into sub problems.
        devide(A, p, q);   //divide left problem into sub problems
        devide(A, q + 1, r); //divide right problem into sub problems
        merger(A, p, q, r);  //merger the sub problem
    }
}

void merger(int A[], int p, int q, int r) {
    int L[] = new int[q - p + 1];
    int R[] = new int[r - q + 0];

    int a1 = 0;
    int b1 = 0;
    for (int i = p; i <= q; i++) {  //store left sub problem in Left temp
        L[a1] = A[i];
        a1++;
    }
    for (int i = q + 1; i <= r; i++) { //store left sub problem in right temp
        R[b1] = A[i];
        b1++;
    }
    int a = 0;
    int b = 0; 
    int c = 0;
    for (int i = p; i < r; i++) {
        if (a < L.length && b < R.length) {
            c = i + 1;
            if (L[a] <= R[b]) { //compare left element<= right element
                A[i] = L[a];
                a++;
            } else {
                A[i] = R[b];
                b++;
            }
        }
    }
    if (a < L.length)
        for (int i = a; i < L.length; i++) {
            A[c] = L[i];  //store remaining element in Left temp into main problem 
            c++;
        }
    if (b < R.length)
        for (int i = b; i < R.length; i++) {
            A[c] = R[i];  //store remaining element in right temp into main problem 
            c++;
        }
}

Ответ 8

Я знаю, что это старый вопрос, но мне хотелось бросить мои мысли о том, что помогло мне понять сортировку слияния.

Есть две большие части для объединения сортировки

Разделение массива на более мелкие куски (разделение)
Объединение массива вместе (покорение)

Роль recurison - это просто разделительная часть.

Я думаю, что смущает большинство людей, так это то, что они думают, что существует много логики в расщеплении и определении того, что нужно разделить, но большая часть фактической логики сортировки происходит в слиянии. Рекурсия просто состоит в том, чтобы разделить и сделать первую половину, а затем вторая половина действительно просто зацикливается, копируя вещи.

Я вижу несколько ответов, в которых упоминаются ключевые слова, но Я бы рекомендовал не связывать слово "поворот" с сортировкой слиянием, потому что это простой способ запутать сортировку слияния с quicksort (которая в значительной степени зависит от выбора "стержень" ). Они оба "делят и побеждают" алгоритмы. Для сортировки слияния деление всегда происходит посередине, тогда как для быстрой сортировки вы можете быть умны с делением при выборе оптимального стержня.

Ответ 9

Когда вы вызываете рекурсивный метод, он не выполняет реальную функцию, а одновременно стекает в стеке. И когда условие не выполняется, оно переходит к следующей строке.

Учтите, что это ваш массив:

int a[] = {10,12,9,13,8,7,11,5};

Итак, ваш метод merge sort будет работать следующим образом:

mergeSort(arr a, arr empty, 0 , 7);
mergeSort(arr a, arr empty, 0, 3);
mergeSort(arr a, arr empty,2,3);
mergeSort(arr a, arr empty, 0, 1);

after this `(low + high) / 2 == 0` so it will come out of first calling and going to next:

    mergeSort(arr a, arr empty, 0+1,1);

for this also `(low + high) / 2 == 0` so it will come out of 2nd calling also and call:

    merger(arr a, arr empty,0,0,1);
    merger(arr a, arr empty,0,3,1);
    .
    .
    So on

Таким образом, все значения сортировки сохраняются в пустом порядке. Это может помочь понять, как работает рекурсивная функция

Ответ 10

Для лучшего понимания сортировки слиянием вы можете воспользоваться этой ссылкой: https://www.hackerearth.com/practice/algorithms/sorting/merge-sort/tutorial/