1

我搜索了很多例子，但还没有找到我的问题到底出在哪里。我正在尝试实现 Cormen intro to algorithms book 中的合并排序算法——这是我目前所处的位置——我尝试输入打印语句来跟踪数组是如何重建的，但我没有看到它。 ..有人可以帮忙吗？代码：

#include <iostream>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;


int p = 0;
int q = 0;
int r = 0;

int getRandom()
{
    int randNum = 0;

    randNum = 1 + rand() % 100;
    return randNum;
}

void populateArray(int * array, int size)
{
    for (int i = 0; i < size; i++) {
        array[i]=getRandom();
    }
}

void merge (int * array, int p, int q, int r) // p = start, q = mid, r = end
{
    int i = 0;  // left array iterator
    int j = 0;  // right array iterator

    int n1 = q - p + 1;
    int n2 = r - q;

   // int arrayL[n1 + 1];
    //int arrayR[n2 + 1];

    int arrayL[n1];
    int arrayR[n2];



    for (i = 0; i < n1; i++) {
        arrayL[i] = array[p + i];
    }

    cout << "TEST ARRAY MS A: ";
    for (int count = 0; count < n1; count++) {
        cout << arrayL[count] << " ";
    }
    cout << endl << endl;

    for (j = 0; j < n2; j++) {
        arrayR[j] = array[q + j + 1];
    }



    cout << "TEST ARRAY MS B: ";
    for (int count = 0; count < n2; count++) {
        cout << arrayR[count] << " ";
    }
    cout << endl << endl;

    //arrayL[n1 + 1] = 1000;
    //arrayR[n2 + 1] = 1000;

    //i = 0;
    //j = 0;

    for (int k = p, i = j = 0; k <= r; k++) {
        if (j >= n2 || (i <= n1 && arrayL[i] <= arrayR[j])) {
            array[k] = arrayL[i];
            i++;

            cout << "TEST ARRAY in loop A: ";
            for (int tempIt = 0; tempIt < r; tempIt++) {
                cout << array[tempIt] << " ";
            }
            cout << endl << endl;

        }
        else {
            array[k] = arrayR[j];
            j++;

            cout << "TEST ARRAY in loop B: ";
            for (int tempIt = 0; tempIt < r; tempIt++) {
                cout << array[tempIt] << " ";
            }
            cout << endl << endl; 
        }

        cout << "TEST ARRAY in loop: ";
        for (int tempIt = 0; tempIt < r; tempIt++) {
            cout << array[tempIt] << " ";
        }
        cout << endl << endl;    
    }
}

void mergeSort (int * array, int p, int r)
{
    if (p < r) {
        q = floor((p + r) / 2);
        mergeSort(array, p, q);
        mergeSort(array, q + 1, r);
        merge(array, p, q, r);
    }
}

int main(int argc, const char * argv[])
{

    unsigned seed = time(0);

    srand(seed);

    int testArray[5];

    populateArray(testArray, 5);


    cout << "TEST ARRAY: ";
    for (int count = 0; count < 5; count++) {
        cout << testArray[count] << " ";
    }
    cout << endl << endl;

    mergeSort(testArray, 0, 4);

    cout << "TEST ARRAY after mergeSort: ";
    for (int count = 0; count < 5; count++) {
        cout << testArray[count] << " ";
    }
    cout << endl << endl;


    return 0;
}
4

0 回答 0