优化的冒泡排序算法比未优化的花费更多时间

Question

我不明白为什么我的冒泡排序算法的优化版本比未优化版本花费不少于时间

这是我的文件：

main.c

- 在这里我创建不同大小的数组并运行两种算法

#define RAND_NUM rand() % 1000;

int main(void) {
    srand(time(nullptr));

    constexpr int arrays_sizes[] = {10'000, 50'000, 100'000};
    constexpr int arrays_sizes_size = sizeof(arrays_sizes) / sizeof(int);

    for (int i = 0; i < arrays_sizes_size; ++i) {
        const int array_size = arrays_sizes[i];
        int *nums = malloc(sizeof(int) * array_size);
        int *nums_copy = malloc(sizeof(int) * array_size);

        for (int i = 0; i < array_size; ++i) {
            nums[i] = RAND_NUM;
        }

        copy_arr(nums_copy, nums, array_size);
        clock_t begin = clock();
        BUBBLE_SORT_RETURN_TYPE steps_count = bubble_sort(nums_copy, array_size);
        clock_t end = clock();

        long int time_spent = end - begin;

        printf("Bubble sort on array size of %d: Time: %ldms | Approximate steps count: %lu\n", array_size, time_spent, steps_count);

        copy_arr(nums_copy, nums, array_size);
        begin = clock();
        steps_count = bubble_sort_2(nums_copy, array_size);
        end = clock();

        time_spent = end - begin;

        printf("Bubble sort V2 on array size of %d: Time: %ldms | Approximate steps count: %lu\n", array_size, time_spent, steps_count);

        free(nums);
        free(nums_copy);
    }

    return EXIT_SUCCESS;
}

bubble_sort.c

- 未优化版本

BUBBLE_SORT_RETURN_TYPE bubble_sort(int *arr, const size_t size) {
    BUBBLE_SORT_RETURN_TYPE steps_count = 0;

    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size - i - 1; ++j) {

            ++steps_count;

            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j + 1);
                ++steps_count;
            }
        }
    }

    return steps_count;
}

bubble_sort_2.c

- 优化版本

BUBBLE_SORT_RETURN_TYPE bubble_sort_2(int *arr, const size_t size) {
    BUBBLE_SORT_RETURN_TYPE steps_count = 0;

    for (int i = 0; i < size; ++i) {
        bool is_sorted = true;

        for (int j = 0; j < size - i - 1; ++j) {

            ++steps_count;

            if (arr[j] > arr[j + 1]) {
                is_sorted = false;
                swap(arr, j, j + 1);
                ++steps_count;
            }
        }

        if (is_sorted) break;
    }

    return steps_count;
}

swap.c

void swap(int *nums, const int i, const int j) {
    const int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

copy_arr.c

void copy_arr(int *into, const int *from, const int size) {
    for (int i = 0; i < size; ++i) {
        into[i] = from[i];
    }
}

#define BUBBLE_SORT_RETURN_TYPE unsigned long int

这是我得到的输出：

Bubble sort on array size of 10000: Time: 104ms | Approximate steps count: 74933780
Bubble sort V2 on array size of 10000: Time: 109ms | Approximate steps count: 74917127
Bubble sort on array size of 50000: Time: 2714ms | Approximate steps count: 1872216503
Bubble sort V2 on array size of 50000: Time: 2801ms | Approximate steps count: 1872215278
Bubble sort on array size of 100000: Time: 11628ms | Approximate steps count: 3203308155
Bubble sort V2 on array size of 100000: Time: 12672ms | Approximate steps count: 3203284719

如您所见，

V2

中的步数比未优化版本少，但需要更多时间。为什么？

这里可能是对如何测量时间的语法误解？

Answer 1

步骤数微小的 0.0007% 减少可能会被每次迭代设置和测试中指令数量的增加所淹没

is_sorted

。

通过对任一版本应用编译器优化，您可能会获得不同且更重要的结果。

优化众所周知的次优算法可能没有什么优点。