计算排序算法中的执行时间 [英] Calculate Execution Times in Sort algorithm

问题描述

我在 C++ 中实现了合并排序和快速排序，我想使用两者中的每一个来获得执行时间，其中许多情况已经排序或未排序 &有不同的尺寸.

I implemented Merge Sort and Quick Sort in C++, and I wanna get the execution times using each of two with many of cases those are already Sorted or not & has different size.

#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;
}

嗯，程序确实运行了，但是打印的执行时间和我预期的不一样.我做的好吗?我想运行这两种算法来显示它们的执行时间，所以我可以用这种方式比较它们的时间复杂性(尽可能不固定排序算法).

Well, the program worked actually, but the execution time printed was not like what I expected. Did I do all right? I wanna run both algorithms to show their execution times and so I could compare their TIME COMPLEXITY in this way (without fixing sort algorithm as much as possible).

推荐答案

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

Your merge sort algorithm is very inefficient: Merge makes a copy of the whole array at the start of each recursive call, a quadratic cost.

在一些非常常见的情况下，快速排序的实现也是病态的慢:如果数组已经排序，枢轴值总是切片中的最小元素，所以递归深度是数组的长度，你得到二次如果不是堆栈溢出的时间复杂度.

The quick sort implementation is also pathologically slow in some very common cases: if the array is already sorted, the pivot value is always the smallest element in the slice, so the recursion depth is the length of the array and you get quadratic time complexity if not a stack overflow.

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

It is difficult to tell without measuring which if these inefficiencies will hurt performance the most, but I would guess MergeSort is the loser.

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

Also if you want to print milliseconds, use this expression:

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

要修复Merge中的问题，修改代码以创建正确大小的向量:

To fix the problem in Merge, modify the code to create a vector of the correct size:

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);
}

这篇关于计算排序算法中的执行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！