我如何打印MergeSort的所有中间步骤？

Question

大约两周前，我在C ++类简介中分配了一个项目，其中涉及使用向量和排序算法。我已经成功实现了所有必需的算法，并且可以通过打印中间步骤和最终排序的所有向量来验证它们是否有效。我唯一的问题是获取合并排序以以下格式打印其中间结果：

[[14，7，3，12，12，9，11，6，2]

[[14，7，3，12] [9，11，6，2]

[[14，7] [3，12] [9，11] [6，2]

[14] [7] [3] [12] [9] [11] [6] [2]

[[7，14] [3，12] [9，11] [2，6]

[[3，7，12，14] [2，6，9，11]

[[2，3，6，7，7，9，11，12，14]

其中第一行和最后一行是原始的和排序的原始向量。

我已经尝试修改矢量打印过程，该过程将合并排序函数从接收到的被调用方接收到的原始数组中取一半来获取两个矢量。它以一种很奇怪的方式打印结果，您将在下面看到。我也放弃了制作一个2D数组的想法，该数组可以容纳所有内容并针对每一行进行迭代。问我应该在哪里调用我的新的和改进的打印功能也很相关...？

以下是我打印合并排序矢量的过程：

/*
    Procedure: printMergeSort
    Purpose:   prints merge sort steps to the console
*/

void printMergeSort(vector <int> left, vector <int> right)
{

    for (int i = 0; i < left.size(); ++i)
    {

        if (i == 0)
            printf("[%d, ", left[i]);
        else if (i < left.size() - 1)
            printf("%d, ", left[i]);
        else
            printf("%d], ", left[i]);

    }

    for (int i = 0; i < right.size(); ++i)
    {

        if (i == 0)
            printf("[%d, ", right[i]);
        else if (i < right.size() - 1)
            printf("%d, ", right[i]);
        else
            printf("%d] \n", right[i]);

    }

}``

以及我的合并和合并排序代码：

/*
    Procedure: merge
    Purpose:   Helper funcrion for mergeSort...
               Sorts the subarrays and merges them
*/

void merge(vector<int>& leftVector, vector<int>& rightVector, vector<int>& vectortoMerge)
{

    int lefttmostValue = leftVector.size();
    int rightmostValue = rightVector.size();
    int i = 0, j = 0, k = 0;

    //printMergeSort(leftVector, rightVector);

    while (j < lefttmostValue and k < rightmostValue)
    {

        if (leftVector[j] < rightVector[k])
        {

            vectortoMerge[i] = leftVector[j];
            //printf("%d ", vectortoMerge[i]); 
            ++j;

        }
        else
        {

            vectortoMerge[i] = rightVector[k];

            //printf("%d ", vectortoMerge[i]);
            ++k;

        }

        ++i;

    }
    while (j < lefttmostValue)
    {

        vectortoMerge[i] = leftVector[j];       
        //printf("%d ", vectortoMerge[i]);
        ++j; ++i;

    }

    while (k < rightmostValue) 
    {

        vectortoMerge[i] = rightVector[k];
        //printf("%d ", vectortoMerge[i]);
        ++k; ++i;

    }

}

/*
    procedure: mergeSort
    Purpose:   Main function for the merge sort algorithm....
               Splits the vector into 2 and makes a call the merge() function
*/

void mergeSort(vector<int>& vectortoSort)
{
    if (vectortoSort.size() <= 1) return;

    int middleElement = vectortoSort.size() / 2;
    vector<int> leftVector;
    vector<int> rightVector;

    for (int j = 0; j < middleElement; ++j)
        leftVector.push_back(vectortoSort[j]);
    for (int j = 0; j < (vectortoSort.size()) - middleElement; ++j)
        rightVector.push_back(vectortoSort[middleElement + j]);

    printMergeSort(leftVector, rightVector);
    printf(", ");
    mergeSort(leftVector);
    mergeSort(rightVector);
    merge(leftVector, rightVector, vectortoSort);


}

上面已经说明了预期的输出，但是当输入这些值时，我得到以下信息：

[[14，7，3，12]，[9，11，6，2] [14，7]，[3，12] [14，[7，[3，[12，[9,11]， [6，2] [9，[11，[6，[2，]

为了解决这个问题，有没有更好的方法？我将非常感谢您的帮助，因为我所有的同事和朋友都为这一努力感到困惑！

谢谢！！

Answer 1

第一个调用正确产生所需的[14, 7, 3, 12], [9, 11, 6, 2]行；然后将第一个递归调用应用于[14, 7, 3, 12]，并且completely在对第二部分进行anything之前（递归地）对那一半进行排序。因此，无法产生所需的[14, 7] [3, 12] [9, 11] [6, 2]行，因为递归将继续处理[14, 7] [3, 12]块，然后才能打印[9, 11] [6, 2]。

要解决此问题，您需要完全从递归转换为广度优先遍历。

Answer 2

问题在于打印时的索引。当数组的大小很小时，您的代码的其他部分将无法到达（对不起，我的英语）：尝试这样的事情

printf("[");
for (int i = 0; i < left.size(); ++i)
{
    if (i != 0)
        printf(", ");
    printf("%d", left[i]);
}
printf("], [");

for (int i = 0; i < right.size(); ++i)
{
    if (i != 0)
        printf(", ");
    printf("%d", right[i]);
}
printf("]\n");

Answer 3

我同意卡尔·克内希特尔的回答。但是有一个出路（艰难的出路）：计算递归深度的每个级别，并将相应的矢量沿着级别索引推入容器；逐级打印容器。这是一个代码段（未优化）：

void print(const vector<int>& vec) {
    printf("[");
    for (auto it = vec.begin(); it != vec.end(); it++) {
        (it == vec.end() - 1) ? printf("%d", *it) : printf("%d, ", *it);
    }
    printf("]");
}

vector<pair<int, vector<int>>> vecs;
static int MaxDepth = 0;

void mergeSort(vector<int>& vectortoSort, int level = 0)
{
    if (level > MaxDepth) MaxDepth = level + 1;
    if (vectortoSort.size() <= 1)
    {
        return;
    }

    int middleElement = vectortoSort.size() / 2;
    vector<int> leftVector;
    vector<int> rightVector;

    for (int j = 0; j < middleElement; ++j)
        leftVector.push_back(vectortoSort[j]);
    for (int j = 0; j < (vectortoSort.size()) - middleElement; ++j)
        rightVector.push_back(vectortoSort[middleElement + j]);

    vecs.push_back(make_pair(level, leftVector));  mergeSort(leftVector, level + 1);
    vecs.push_back(make_pair(level, rightVector)); mergeSort(rightVector, level + 1);

    merge(leftVector, rightVector, vectortoSort);
    vecs.push_back(make_pair(MaxDepth +1 - level, vectortoSort));
}

void main()
{
    vector<int> vec{ 14, 7, 3, 12, 9, 11, 6, 2 };
    vecs.push_back(make_pair(-1, vec));
    mergeSort(vec); 
    for (int i = -1; i < MaxDepth + 2; i++) {
        for (const auto& e : vecs) {
            if (e.first == i)
            {
                print(e.second);
                cout << "  ";
            }
        }
        cout << "\n";
    }
}

以下是屏幕截图：

Answer 4

真棒答案！！！

对于每种算法，我还需要将向量输出到文件中。这是我使用@seccpur的打印方法得到的内容：

[，14，7，312] [，9，11，62]

[，147] [，312] [，911] [，62]

[14] [7] [3] [12] [9] [11] [6] [2]

[，714] [，312] [，911] [，26]

[，3，7，1214] [，2，6，911]

[，2，3，6，7，9，9，1214]

如何使@seccpur的打印代码适用于我的ofstream对象？