Как распечатать все промежуточные этапы MergeSort?

Question

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

[14, 7, 3, 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, 9, 11, 12, 14]

где первая и последняя строки являются исходным и отсортированным исходным вектором.

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

Ниже описана моя процедура печати векторов сортировки слиянием:

/*
    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

Потрясающие ответы, ребята!

Мне также нужно вывести мой вектор в файл для каждого алгоритма. Вот что я получаю, используя метод печати @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, 11, 1214]

Как заставить работать код печати @seccpur для моего объекта ofstream?

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

При первом вызове получается нужная строка [14, 7, 3, 12], [9, 11, 6, 2];затем первый рекурсивный вызов применяется к [14, 7, 3, 12] и полностью сортирует эту половину (рекурсивно) до того, как что-либо будет сделано со второй половиной. Таким образом, невозможно получить нужную строку [14, 7] [3, 12] [9, 11] [6, 2], потому что рекурсия будет продолжать обрабатывать куски [14, 7] [3, 12] до того, как [9, 11] [6, 2] сможет распечатать.

Чтобы исправить это, вам нужно полностью отойти от рекурсиив обход в ширину.