优化冒泡排序——我错过了什么？

Question

我正在尝试了解冒泡排序算法的可能优化方法。我知道有更好的排序方法，但我只是好奇

为了测试我使用 std::chrono 的效率。该程序对 10000 number long int 数组排序 30 次并打印平均排序时间。在每次迭代中随机选择数字（最多 10000）。这是代码，没有优化：

#include <iostream>
#include <ctime>
#include <chrono>
using namespace std;



int main() {


    //bubble sort
    srand(time(NULL));

    chrono::time_point<chrono::steady_clock> start, end;

    const int n = 10000;
    int i,j, last, tests = 30,arr[n];
    long long total = 0;
    bool out;

    while (tests-->0) {


        for (i = 0; i < n; i++) {
            arr[i] = rand() % 1000;
        }


        j = n;

        start = chrono::high_resolution_clock::now();
        while(1){

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

                if (arr[i + 1] < arr[i]) {
                    swap(arr[i + 1], arr[i]);
                    out = 1;
                }
            }

            if (!out) {
                    break;
            }

            //j--;

        }


        end = chrono::high_resolution_clock::now();

        total += chrono::duration_cast<chrono::nanoseconds>(end - start).count();
        cout << "Remaining :"<<tests << endl;

    }

    cout << "Average  :" << total / static_cast<double>(30)/1000000000<<" seconds"; // tests(30)  + nanosec -> sec


    cin.sync();
    cin.ignore();
    return 0;
}

我得到 0.17 秒的平均排序时间。

如果我取消注释第 47(j--;) 行以避免比较已经排序的数字，我得到 0.12 排序时间，这是可以理解的。

如果我记得交换发生的最后位置，我知道在那个索引之后，元素被排序，因此可以在进一步的迭代中排序到那个位置。 post 的第二部分对此有更好的解释：。这是实现新的可能优化的代码：

#include <iostream>
#include <ctime>
#include <chrono>
using namespace std;



int main() {


    //bubble sort
    srand(time(NULL));

    chrono::time_point<chrono::steady_clock> start, end;

    const int n = 10000;
    int i,j, last, tests = 30,arr[n];
    long long total = 0;
    bool out;

    while (tests-->0) {


        for (i = 0; i < n; i++) {
            arr[i] = rand() % 1000;
        }


        j = n;

        start = chrono::high_resolution_clock::now();
        while(1){

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

                if (arr[i + 1] < arr[i]) {
                    swap(arr[i + 1], arr[i]);
                    out = 1;
                    last = i;
                }
            }

            if (!out) {
                    break;
            }

            j = last + 1;

        }


        end = chrono::high_resolution_clock::now();

        total += chrono::duration_cast<chrono::nanoseconds>(end - start).count();
        cout << "Remaining :"<<tests << endl;

    }

    cout << "Average  :" << total / static_cast<double>(30)/1000000000<<" seconds"; // tests(30)  + nanosec -> sec


    cin.sync();
    cin.ignore();
    return 0;
}

注意第 40 和 48 行。问题来了：平均时间现在又是 0.17 秒左右。我的代码有问题，还是我遗漏了什么？

更新：

我用 10 倍以上的数字进行排序，现在得到以下结果：无优化：19.3 秒第一次优化（j--）：14.5秒第二次（假设）优化（j=last+1）：17.4 秒；

根据我的理解，第二种方法在任何情况下都应该比第一种好，但数字说明了一些不同的东西。

Answer 1

嗯...问题是这个问题可能没有正确或错误的答案。

首先，当你只比较 10000 个元素时，你不能真正称之为效率测试。尝试比较更多数量的元素 - 可能是 500000（尽管您可能需要为此动态分配一个数组）。

其次，可能是编译器。编译器经常尝试优化一些东西，以便程序执行运行更流畅、更快。

优化冒泡排序——我错过了什么？

Optimizing bubble sort - What am I missing?

c++

sorting

algorithm

optimization

bubble-sort