计算排序算法中的执行时间

Question

我在 C++ 中实现了合并排序和快速排序，我想使用两者中的每一个来获取执行时间，其中许多情况已经排序或未排序并且大小不同。

#include <iostream>
#include <ctime>
#include <vector>
#include <algorithm>

using namespace std;

void Merge(vector<int>& s, int low, int mid, int high) {
    int i = low;
    int j = mid + 1;
    int k = low;
    vector<int> u(s);

    while (i <= mid && j <= high) {
        if (s.at(i) < s.at(j)) {
            u.at(k) = s.at(i);
            i++;
        } else {
            u.at(k) = s.at(j);
            j++;
        }
        k++;
    }
    if (i > mid) {
        for (int a = j; a < high + 1; a++) {
            u.at(k) = s.at(a);
            k++;
        }
    } else {
        for (int a = i; a < mid + 1; a++) {
            u.at(k) = s.at(a);
            k++;
        }
    }
    for (int a = low; a < high + 1; a++)
        s.at(a) = u.at(a);
}

void MergeSort(vector<int>& s, int low, int high) {
    int mid;
    if (low < high) {
        mid = (low + high) / 2;
        MergeSort(s, low, mid);
        MergeSort(s, mid + 1, high);
        Merge(s, low, mid, high);
    }
}

void swap(int& a, int& b) {
    int tmp = a;
    a = b;
    b = tmp;
}

void Partition(vector<int>& s, int low, int high, int& pvpoint) {
    int j;
    int pvitem;

    pvitem = s.at(low);
    j = low;
    for (int i = low + 1; i <= high; i++) {
        if (s.at(i) < pvitem) {
            j++;
            swap(s.at(i), s.at(j));
        }
        pvpoint = j;
        swap(s.at(low), s.at(pvpoint));
    }
}

void QuickSort(vector<int>& s, int low, int high) {
    int pvpoint;
    if (high > low) {
        Partition(s, low, high, pvpoint);
        QuickSort(s, low, pvpoint - 1);
        QuickSort(s, pvpoint + 1, high);
    }
}

int main() {
    vector<int> CaseSize(20);

    for (int i = 0; i < 10; i++) { //10 Arrays those are sorted
        CaseSize.at(i) += (i + 1) * 500;
    }

    for (int i = 10; i < 20; i++) { //rest 10 those are not sorted
        CaseSize.at(i) += (i + 1) * 5000;
    }

    cout << "------------------Sorted------------------\n\n";
    cout << "      Quick Sort       Merge Sort\n";
    for (int i = 0; i < 10; i++) {
        vector<int> Arr(CaseSize.at(i));
        Arr.front() = rand() % Arr.size();
        for (int j = 1; j < Arr.size(); j++) {
            Arr.at(j) = ((17 * Arr.at(j - 1) + 43) % (Arr.size() * 5));
        }
        vector<int> Arr2(Arr);

        sort(Arr.begin(), Arr.end());
        sort(Arr2.begin(), Arr2.end());

        cout << "N : " << CaseSize.at(i) << "    ";
        clock_t start = (int)clock();
        QuickSort(Arr, 0, Arr.size() - 1);
        printf("%0.5fms", (float)(clock() - start) / CLOCKS_PER_SEC);
        cout << "\t\t";

        clock_t start2 = (int)clock();
        MergeSort(Arr2, 0, Arr2.size() - 1);
        printf("%0.5fms", (float)(clock() - start) / CLOCKS_PER_SEC);
        cout << endl;
    }
    cout << endl;
    cout << "------------------Random------------------\n\n";
    cout << "        Quick Sort     Merge Sort\n";
    for (int k = 10; k < 20; k++) {
        vector<int> Arr(CaseSize.at(k));
        Arr.front() = rand() % Arr.size();
        for (int l = 1; l < Arr.size(); l++) {
            Arr.at(l) = ((17 * Arr.at(l - 1) + 43) % (Arr.size() * 5));
        }
        vector<int> Arr2(Arr);

        cout << "N : " << CaseSize.at(k) << "    ";

        clock_t start = (int)clock();
        QuickSort(Arr, 0, Arr.size() - 1);
        printf("%0.5fms", (float)(clock() - start) / CLOCKS_PER_SEC);

        cout << "\t\t";

        clock_t start2 = (int)clock();
        MergeSort(Arr2, 0, Arr2.size() - 1);
        printf("%0.5fms", (float)(clock() - start) / CLOCKS_PER_SEC);
        cout << endl;
    }
    return 0;
}

好吧，程序确实有效，但打印的执行时间与我预期的不一样。我做的好吗？我想运行两种算法都显示它们的执行时间，所以我可以用这种方式比较它们的 时间复杂度（尽可能不固定排序算法）。

Answer 1

您的合并排序算法非常效率低下：Merge在每次递归调用开始时复制整个数组，二次成本。

在一些非常常见的情况下，快速排序的实现也非常慢：如果数组已经排序，主元值总是切片中的最小元素，所以递归深度是数组的长度，你如果不是 堆栈溢出.

，则获得二次时间复杂度

如果不衡量这些低效率对性能的影响最大，则很难判断，但我猜 MergeSort 是输家。

另外如果你想打印毫秒数，使用这个表达式：

printf("%0.5fms", (clock() - start) * 1000.0 / CLOCKS_PER_SEC);

要解决 Merge 中的问题，请修改代码以创建正确大小的向量：

void Merge(vector<int>& s, int low, int mid, int high) {
    int i = low;
    int j = mid + 1;
    int k = 0;
    vector<int> u(high + 1 - low);

    while (i <= mid && j <= high) {
        if (s.at(i) < s.at(j)) {
            u.at(k) = s.at(i);
            i++;
        } else {
            u.at(k) = s.at(j);
            j++;
        }
        k++;
    }
    if (i > mid) {
        while (j <= high) {
            u.at(k) = s.at(j);
            j++;
            k++;
        }
    } else {
        while (i <= mid) {
            u.at(k) = s.at(i);
            i++;
            k++;
        }
    }
    for (i = low, k = 0; i <= high; i++, k++)
        s.at(i) = u.at(k);
}

Answer 2

你做错了。首先，您需要添加 include 。您可以通过以下方式获取不同算法的执行时间： x 是数组的大小。

include <time.h>
int main(){
struct timeval stop,start;
int arr[x];
for(int i=0;i<x;i++)
    arr[i]=i+1;
printf("This is the Array created with sorted integer(Sorted  Data)\n\n");
gettimeofday(&start,NULL);
selectionSort(arr,x);
gettimeofday(&stop,NULL);
printf("Time taken for selection sort is: %ld microseconds\n",(stop.tv_sec- 
start.tv_sec)*1000000+stop.tv_usec-start.tv_usec);

gettimeofday(&start,NULL);
bubbleSort(arr,x);
gettimeofday(&stop,NULL);
printf("Time taken for Bubble sort is: %ld microseconds\n",(stop.tv_sec- 
start.tv_sec)*1000000+stop.tv_usec-start.tv_usec);

gettimeofday(&start,NULL);
quickSort(arr,0,9999);
gettimeofday(&stop,NULL);
printf("Time taken for Quick sort is: %ld microseconds\n",(stop.tv_sec- 
start.tv_sec)*1000000+stop.tv_usec-start.tv_usec);

gettimeofday(&start,NULL);
heapSort(arr,x);
gettimeofday(&stop,NULL);
printf("Time taken for Heap sort is: %ld microseconds\n",(stop.tv_sec- 
start.tv_sec)*1000000+stop.tv_usec-start.tv_usec);
}

计算排序算法中的执行时间

Calculate Execution Times in Sort algorithm

c++

mergesort

quicksort

time-complexity