C中冒泡排序算法的运行时

Question

您好，我正在我的大学上一门关于数据结构和算法的讲座。我正在做关于分析排序算法的作业。作业需要包含测量运行算法时间的报告。 TA给了我们三个30000个整数的数据集（升序，降序，随机）

我认为对数据进行降序排序比对随机排序的数据进行排序要花更多的时间。但是在我的冒泡排序算法中，结果是相反的。

数字降序排序需要2.453s实时和2.409s用户时间，随机排序需要3.217s实时和3.159s用户时间。这个结果也和我的选择排序算法有关。降序排列的数字不是最坏的情况吗？

//file is opened at main function
int* bubble_prj4(FILE *fp_in)
{
    int i, j, temp;

    //arr is declared in header file
    arr = (int*)malloc(sizeof(int) * 30000);
    fread(arr, sizeof(int), 30000, fp_in);
    for(i = 0; i < 29999; i++)
        for(j = 29999; j > i; j--)
            if(arr[j] < arr[j - 1])
            {
                temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
            }
    return arr;
}

第一次在这里提问。我不知道我这样做的方式是否正确。

Answer 1

我运行你的测试。以下是我对大小为 30,000 的三个不同数据集的结果：

  dataset  |  time (s)  |   swaps
-----------+------------+----------
random     |  3.588447  | 221476595
descending |  2.588694  | 449985000
ascending  |  1.582666  |         0

这是怎么回事？为什么运行domized 数据集比 "worst-case" 降序数据集慢？

答案似乎是branch prediction. The CPU makes a guess to see which branch will be taken in the code, executes it, and is correct 100% of the time in the descending dataset. This leads to significant performance increases and has been more elegantly explained before。

话虽如此，例程涉及相同数量的比较，时间复杂度在所有情况下都是 O(n²)。

C中冒泡排序算法的运行时

Runtime of Bubble sort algorithms in C

c

bubble-sort

time-complexity