Пытаясь понять программу сортировки слиянием - PullRequest
Новая
       5

Пытаясь понять программу сортировки слиянием

0 голосов
/ 09 июня 2019

Я очень стараюсь понять программу сортировки слиянием. Чтобы понять, я написал эту программу, но не могу понять вывод.Было бы очень полезно, если бы кто-то объяснил вывод.Я понял только до mid=0. 

 #include <iostream>

 using namespace std;

 void check(int c, int d) {
     cout << "C=" << c << " D=" << d << endl;

     if (c < d) {
         int mid = (c + d) / 2;
         cout << "mid=" << mid << endl;
         check(c, mid);
         check(mid + 1, d);
     }
}

int main() {
    // int a[12] = { 2, 3, 1, 6, 9, 112, 113, 224, 225, 226, 332, 2303 };

    check(0, 5);
    return 0;
}

Вывод: 

C=0 D=5
mid=2
C=0 D=2
mid=1
C=0 D=1
mid=0
C=0 D=0
C=1 D=1
C=2 D=2
C=3 D=5
mid=4
C=3 D=4
mid=3
C=3 D=3
C=4 D=4
C=5 D=5

1 Ответ

0 голосов
/ 10 июня 2019

Обратите внимание, что это основано на сортировке слиянием сверху вниз, которая популярна для обучения, но большинство библиотек используют вместо этого сортировку слиянием снизу вверх. Что касается выходных данных, сортировка слиянием сверху вниз генерирует и помещает индексы в стек, что приводит к упорядочению по глубине в первую очередь, слева вначале. Объединение не происходит до тех пор, пока не будут произведены 2 прогона размером 1 Я изменил код, чтобы показать уровень рекурсии l , и если рекурсивный вызов был первым или вторым x : 

#include <iostream>

using namespace std;

void check(int c, int d, int l, int x) {
    if(c >= d){
        cout << "l = " << l << "  x = " << x;
        cout << "  c = " << c << "         d = " << d << endl;
        return;
    }
    int m = (c + d) / 2;
    cout << "l = " << l << "  x = " << x;
    cout << "  c = " << c << "  m = " << m << "  d = " << d << endl;
    check(c, m, l+1, 1);
    check(m + 1, d, l+1, 2);
}

int main() {
    check(0, 5, 0, 0);
    return 0;
}

Это вывод: 

l = 0  x = 0  c = 0  m = 2  d = 5
l = 1  x = 1  c = 0  m = 1  d = 2
l = 2  x = 1  c = 0  m = 0  d = 1
l = 3  x = 1  c = 0         d = 0
l = 3  x = 2  c = 1         d = 1
l = 2  x = 2  c = 2         d = 2
l = 1  x = 2  c = 3  m = 4  d = 5
l = 2  x = 1  c = 3  m = 3  d = 4
l = 3  x = 1  c = 3         d = 3
l = 3  x = 2  c = 4         d = 4
l = 2  x = 2  c = 5         d = 5
...