C语言 我的InsertionSort程序运行速度比MergeSort程序快，即使输入量很大,为什么？

wljmcqd8  于 2022-12-11  发布在  其他
关注(0)|答案(1)|浏览(118)

我是一个初学者，我想找出我的代码执行所花费的时间，并找出插入排序（IS）是否比合并排序（MS）花费更多的时间（对于足够大的输入，它应该花费更多的时间）。
所以我写了一个递归IS算法：

void Insertion_Sort(int *A, int n) {
    if (n < SIZE - 1) {
        int j = n;
        int key = A[j + 1];
        while (j >= 0 && A[j] > key) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = key;
        n++;
        Insertion_Sort(A, n);
    }
}

int main() { 
    struct timeval tv1, tv2;
    int array[SIZE];

    printf("Enter the elements to be sorted\n");
    freopen("input1.txt", "r", stdin);
    freopen("output1.txt", "w", stdout);
    for (int i = 0; i < SIZE; i++) {
        scanf("%d", array + i);
    }
    gettimeofday(&tv1, NULL);
    for (int i = 0; i < 1000; i++) {
        Insertion_Sort(array, 0);
    }
    gettimeofday(&tv2, NULL);
    printf("The sorted array is :\n");
    for (int i = 0; i < SIZE; i++) {
        printf("%d\n", array[i]);
    }
    printf("The microsecond 1 is %f\n", (double)(tv2.tv_usec));
    printf("The microsecond 2 is %f\n", (double)(tv1.tv_usec));
    printf("Total time = %f seconds\n",
           (double)(tv2.tv_usec - tv1.tv_usec) / 1000000 +
           (double)(tv2.tv_sec - tv1.tv_sec));
}

这是代码，运行时间为0.015秒
我还为MergeSort编写了一个代码：

void Merge(int *Array, int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;
    int Arr_1[n1 + 1];
    int Arr_2[n2 + 1];

    for (int i = 0; i < n1; i++) {
        Arr_1[i] = Array[p + i];
    }
    for (int i = 0; i < n2; i++) {
        Arr_2[i] = Array[q + i + 1];
    }
    Arr_1[n1] = __INT_MAX__;
    Arr_2[n2] = __INT_MAX__;
    int i = 0;
    int j = 0;
    for (int k = p ; k <= r; k++) {
        if (Arr_1[i] < Arr_2[j]) {
            Array[k] = Arr_1[i];
            i++;
        } else {
            Array[k] = Arr_2[j];
            j++;
        } 
    }
}

void Merge_Sort(int *Array, int p, int r) {
    if (p < r) { 
        int mid;
        mid = (p + r) / 2;
        Merge_Sort(Array, p, mid);
        Merge_Sort(Array, mid + 1, r);
        Merge(Array, p, mid, r);
    }
}

//driver code
int main() {
    struct timeval tv1, tv2;
    int Array[SIZE];

    printf("Enter the array for Merging Operation:\n");
    freopen("input1.txt", "r", stdin);
    freopen("output3.txt", "w", stdout);
    for (int i = 0; i < SIZE; i++) {
        scanf("%d", &Array[i]);
    }
    gettimeofday(&tv1, NULL);

    for (int i = 0; i < 1000; i++) {
        Merge_Sort(Array, 0, SIZE - 1);
    }
    gettimeofday(&tv2, NULL);
    printf("The sorted array :\n");
    for (int i = 0; i < SIZE; i++) {
        printf("%d\n", Array[i]);
    }
    printf("The microsecond is %f\n", (double)(tv2.tv_usec));
    printf("The microsecond is %f\n", (double)(tv1.tv_usec));
    printf("\n\nTotal time = %f seconds\n",
           (double)(tv2.tv_usec - tv1.tv_usec) / 1000000 +
           (double)(tv2.tv_sec - tv1.tv_sec));
}

这一个给出了0. 06秒的运行时间，我想了解为什么MS比IS慢，尽管它应该更快。
我不太明白定时码位是如何工作的，但无论我给它多大的输入，它都显示0。所以，为了显示结果，我循环了1000次。我认为可能的原因是数组在循环中的第一次调用时就已经排序了，并且因为IS在最好的情况下是线性的，而MS是**nlg（n）**在所有情况下它都运行得更快。这可能吗？如果有人能告诉我如何计时我的代码，我将非常有帮助。提前感谢

c

1条答案

按热度按时间
cvxl0en2

cvxl0en21#

测试代码中的问题是您重复对同一数组排序1000次：时间复杂度为O（n），而时间复杂度为O（n. log（n）），因此，在任何情况下，MergeSort的时间复杂度都是O（n.log（n））**。
为了进行更可靠的测试，您应该制作未排序数组的副本。
以下是修改后的基准测试：

#include <errno.h>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>

#define SIZE    1024
#define REPEAT  1000

void Insertion_Sort(int *A, int n, int last) {
    if (n < last) {
        int j = n;
        int key = A[j + 1];
        while (j >= 0 && A[j] > key) {
            A[j + 1] = A[j];
            j--;
        }
        A[j + 1] = key;
        n++;
        Insertion_Sort(A, n, last);
    }
}

void Merge(int *Array, int p, int q, int r) {
    int n1 = q - p + 1;
    int n2 = r - q;
    int Arr_1[n1 + 1];
    int Arr_2[n2 + 1];

    for (int i = 0; i < n1; i++) {
        Arr_1[i] = Array[p + i];
    }
    for (int i = 0; i < n2; i++) {
        Arr_2[i] = Array[q + i + 1];
    }
    Arr_1[n1] = __INT_MAX__;
    Arr_2[n2] = __INT_MAX__;
    int i = 0;
    int j = 0;
    for (int k = p ; k <= r; k++) {
        if (Arr_1[i] < Arr_2[j]) {
            Array[k] = Arr_1[i];
            i++;
        } else {
            Array[k] = Arr_2[j];
            j++;
        }
    }
}

void Merge_Sort(int *Array, int p, int r) {
    if (p < r) {
        int mid;
        mid = (p + r) / 2;
        Merge_Sort(Array, p, mid);
        Merge_Sort(Array, mid + 1, r);
        Merge(Array, p, mid, r);
    }
}

//driver code
int main() {
    struct timeval tv1, tv2;
    double IS_time, MS_time;
    FILE *fp;
    int SampleArray[SIZE];
    int Array1[SIZE];
    int Array3[SIZE];

    fp = fopen("input1.txt", "r");
    if (fp == NULL) {
        fprintf(stderr, "cannot open input1.txt: %s\n", strerror(errno));
        return 1;
    }
    for (int i = 0; i < SIZE; i++) {
        if (fscanf(fp, "%d", &SampleArray[i]) != 1)
            SampleArray[i] = i * i * i % SIZE;
    }
    fclose(fp);
    gettimeofday(&tv1, NULL);
    for (int i = 0; i < REPEAT; i++) {
        memcpy(Array1, SampleArray, sizeof Array1);
        Insertion_Sort(Array1, 0, SIZE - 1);
    }
    gettimeofday(&tv2, NULL);
    IS_time = ((double)(tv2.tv_usec - tv1.tv_usec) / 1000000 +
               (double)(tv2.tv_sec - tv1.tv_sec));
    for (int i = 1; i < SIZE; i++) {
        if (Array1[i - 1] > Array1[i]) {
            printf("InsertionSort error at %d: %d <-> %d\n",
                   i, Array1[i - 1], Array1[i]);
            break;
        }
    }

    gettimeofday(&tv1, NULL);
    for (int i = 0; i < REPEAT; i++) {
        memcpy(Array3, SampleArray, sizeof Array3);
        Merge_Sort(Array3, 0, SIZE - 1);
    }
    gettimeofday(&tv2, NULL);
    MS_time = ((double)(tv2.tv_usec - tv1.tv_usec) / 1000000 +
               (double)(tv2.tv_sec - tv1.tv_sec));
    for (int i = 1; i < SIZE; i++) {
        if (Array3[i - 1] > Array3[i]) {
            printf("MergeSort error at %d: %d <-> %d\n",
                   i, Array3[i - 1], Array3[i]);
            break;
        }
    }

    fp = fopen("output1.txt", "w");
    if (fp == NULL) {
        fprintf(stderr, "cannot open output1.txt: %s\n", strerror(errno));
        return 1;
    }
    for (int i = 0; i < SIZE; i++) {
        fprintf(fp, "%d\n", Array1[i]);
    }
    fclose(fp);

    fp = fopen("output3.txt", "w");
    if (fp == NULL) {
        fprintf(stderr, "cannot open output3.txt: %s\n", strerror(errno));
        return 1;
    }
    for (int i = 0; i < SIZE; i++) {
        fprintf(fp, "%d\n", Array3[i]);
    }
    fclose(fp);

    printf("InsertionSort total time = %f seconds\n", IS_time);
    printf("MergeSort total time =     %f seconds\n", MS_time);
    return 0;
}

SIZE=1024时的输出：

InsertionSort total time = 0.110109 seconds
MergeSort total time =     0.054474 seconds

SIZE=4096的输出：

InsertionSort total time = 2.057987 seconds
MergeSort total time =     0.276475 seconds

大小=16384时的输出：

InsertionSort total time = 28.658141 seconds
MergeSort total time =     1.297120 seconds

这些时间安排与预期的复杂性一致：时间复杂度为O（n +1），时间复杂度为O（n +1），时间复杂度为O（n +1）。

赞(0）分享  回复(0）举报  2022-12-11
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备2022004421号-2 NULL123 https://www.null123.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com