c ++排序算法持续时间

Question

我一直在努力计算这些排序算法的持续时间.我将所有排序方法循环2000次,然后将总持续时间分成2000,以获得适当的持续时间值.问题是; 它没有显示排序方法的特定代码部分所用的确切时间值.我的意思是duration变量通过程序流显示增加的值.例如,对于N = 10000,insertionSort()给出0.000635,mergeSort()给出0.00836并heapSort()给出0.018485,当我改变它们的顺序时duration,无论算法类型如何,仍然通过程序上升.我尝试为每个进程提供不同的持续时间值,但这不起作用.有人可以帮助我理解这个问题,还是有其他时间测量风格？

对不起,如果这是一个愚蠢的问题和我的坏语法.

int main(){

    srand(time(NULL));

    int N, duration;

    cout << endl << "N : ";
    cin >> N; // N is array sze.
    cout << endl;

    // a4 would be the buffer array (for calculating proper duration).
    int *a1 = new int[N];
    int *a2 = new int[N];
    int *a3 = new int[N];
    int *a4 = new int[N];

    cout << endl << "Unsorted array : " << endl;

    for (int i = 0; i < N; i++){

        a4[i] = rand() % 100;
        cout << a4[i] << " ";
    }

/*------------------------------------------------------------------------------*/

    cout << endl << endl <<"Sorting with Insertion Sort, please wait..." << endl;

    for(int i = 0; i < 2000; i++){

        a1 = a4;

        duration = clock();
        insertionSort(a1, N - 1);
        duration += clock() - duration;
    }

    cout << endl << "Insertion sort : " << endl;

    print(a1, N);

    cout << endl << endl << "Approximate duration for Insertion Sort : ";
    cout << (double) (duration / 2000) / CLOCKS_PER_SEC;
    cout << " s." << endl;

/*------------------------------------------------------------------------------*/

    cout << endl << endl << "Sorting with Merge Sort, please wait..." << endl;

    for(int i = 0; i < 2000; i++){

        a2 = a4;

        duration = clock();
        mergeSort(a2, 0, N - 1);
        duration += clock() - duration;
    }

    cout << endl << "Merge sort : " << endl;

    print(a2, N);

    cout << endl << endl << "Approximate duration for Merge Sort : ";
    cout << (double) (duration / 2000) / CLOCKS_PER_SEC;
    cout << " s."<< endl << endl;

/*------------------------------------------------------------------------------*/

    cout << endl << endl << "Sorting with Heap Sort, please wait..." << endl;

    for(int i = 0; i < 2000; i++){

        a3 = a4;
        duration = clock();
        heapSort(a3, N);
        duration += clock() - duration;
    }

    cout << endl << "Heap sort : " << endl;

    print(a3, N);

    cout << endl << endl << "Approximate duration for Heap Sort : ";
    cout << (double) (duration / 2000) / CLOCKS_PER_SEC;
    cout << " s."<< endl << endl;

    return 0;
}

Answer 1

程序中的错误是您在整个循环中重置持续时间.处理时间的更简洁方法是将duration变量修改放在for循环之外.例如:

duration = clock();
for(int i = 0; i < 2000; i++){
    a2 = a4;
    mergeSort(a2, 0, N - 1);
}
duration = clock() - duration

编辑:忘了删除循环内的部分.现在修复了.