algorithm - 数字数组的最优冒泡排序算法

Question

修复正整数 n 和 k。

设 A 是一个长度为 n 的数组，其中 A[i] 是一个长度为 k 的数组，其中每个条目都是n-i。例如，对于 n=5 和 k=1，这只是

[ [5] , [4] , [3] , [2] , [1] ]

对于n=5 和k=2，这是

[ [5,5] , [4,4] , [3,3] , [2,2] , [1,1] ]

目标是通过交换相邻数组中的数字来对这个数组数组进行冒泡排序(例如，将 A[i][j1] 与 A[i+1][j2]< 交换) 直到 A[i] 的每个条目对于每个 i 都是 i+1。

问题是:需要多少次交换以及最佳算法是什么？

注意: 有很多很多更好的排序算法可供使用。但是，对于这个问题，我只对如上所述应用冒泡排序感兴趣。我只能交换相邻数组中的条目，而且我只对必要的此类交换的最少数量感兴趣。我非常感谢对其他排序算法的所有建议，但这是我试图理解的问题。

示例:

对于 k=1，这是众所周知的。交换的次数是A的倒置数作为一个排列，所以交换的最小次数是二项式系数(n choose 2) = n(n-1)/2 这可以通过交换任何乱序对来实现:A[i] > A[j]。对于第一个示例，这是一个最佳的冒泡排序:

[ [5] , [4] , [3] , [2] , [1] ]
[ [4] , [5] , [3] , [2] , [1] ]
[ [4] , [5] , [2] , [3] , [1] ]
[ [4] , [2] , [5] , [3] , [1] ]
[ [4] , [2] , [5] , [1] , [3] ]
[ [4] , [2] , [1] , [5] , [3] ]
[ [4] , [1] , [2] , [5] , [3] ]
[ [1] , [4] , [2] , [5] , [3] ]
[ [1] , [4] , [2] , [3] , [5] ]
[ [1] , [2] , [4] , [3] , [5] ]
[ [1] , [2] , [3] , [4] , [5] ]

对于 k=2，使用相同的策略会给出 2(n 选择 2) 所需的交换范围。对于上面的示例，这意味着 20 交换。但是有一个解决方案只使用 15 交换:

[ [5,5] , [4,4] , [3,3] , [2,2] , [1,1] ]
[ [5,4] , [5,4] , [3,3] , [2,2] , [1,1] ]
[ [5,4] , [3,4] , [5,3] , [2,2] , [1,1] ]
[ [5,4] , [3,4] , [2,3] , [5,2] , [1,1] ]
[ [5,4] , [3,4] , [2,3] , [1,2] , [5,1] ]
[ [5,4] , [3,4] , [2,1] , [3,2] , [5,1] ]
[ [5,4] , [3,1] , [2,4] , [3,2] , [5,1] ]
[ [1,4] , [3,5] , [2,4] , [3,2] , [5,1] ]
[ [1,4] , [3,2] , [5,4] , [3,2] , [5,1] ]
[ [1,4] , [3,2] , [2,4] , [3,5] , [5,1] ]
[ [1,4] , [3,2] , [2,4] , [3,1] , [5,5] ]
[ [1,4] , [3,2] , [2,1] , [3,4] , [5,5] ]
[ [1,4] , [1,2] , [2,3] , [3,4] , [5,5] ]
[ [1,1] , [4,2] , [2,3] , [3,4] , [5,5] ]
[ [1,1] , [2,2] , [4,3] , [3,4] , [5,5] ]
[ [1,1] , [2,2] , [3,3] , [4,4] , [5,5] ]

此解决方案对于 n=5 和 k=2 是最优的(通过蛮力证明找到所有解决方案)。对于 n=6，最佳解决方案采用 22 交换，但该解决方案看起来不如 n=5 的解决方案(按照右 5，然后左 1，然后右 5，等等)，所以我仍然不知道最佳策略，更不用说交换次数的公式或更好的界限了。

这几天我一直在思考这个问题，但没有想出任何有启发性的东西。如果有人对此问题有任何想法，请分享。我会很高兴了解更多关于 k=2 案例的信息。对于一般情况的任何想法甚至更好。

编辑:如果我不能按照您的喜好提出这个问题，我深表歉意，但这里有一个尝试:对排列进行排序所需的冒泡排序的数量是组合学和数论中非常重要的统计量，称为排列的反转数.您可以使用更好的算法对乱序排列进行排序，但这是为您提供代数意义的算法。如果这没有帮助，也许这个相关的 SO 帖子可能:What is a bubble sort good for?

---

更新:oldest answer below给出交换次数的下限(和上限)。 second oldest answer给出了一个非常接近这个下限的算法(通常达到它)。如果有人可以改进边界，或者更好地证明下面给出的算法是最优的，那就太好了。

Answer 1

这不是最佳答案，但我想分享我的尝试，因为有人可能会改进它。我没想过要找到一个公式来计算最小交换次数，而是寻找最佳算法。该算法基于k = 2。

基本思想是基于信息增益。让我们假设 A = {[i,j] : 1<=i<=n, 1<=j<=n} 代表一个配置。在每个步骤中，我们有 4 * (n-1) 种可能的交换以从一种配置移动到另一种配置。例如，如果 n = 2(即 A = [ {2,2}, {1,1} ] )，那么我们有 4 种可能的交换 A[0][0] <-> A[1][0], A [0][0] <-> A[1][1]、A[0][1] <-> A[1][0] 和 A[0][1] <-> A[1] [1].因此，我们的目标是在需要从一种配置移动到另一种配置时选择具有高信息增益的交换。

棘手的部分将是“如何计算信息增益”。在我的解决方案(如下)中，信息增益基于值与其正确位置的距离。让我向您展示我的代码(用 C++ 编写)以理解我想说的内容:

const int n = 5;
const int k = 2;

int gain(int item, int from, int to)
{
    if (to > from)
        return item - to;
    else
        return to - item ;
}

void swap(int &x, int &y)
{
    int temp = x;
    x = y;
    y = temp;
}

void print_config (int A[][k])
{
    cout << "[";
    for (int i=0; i<n; i++) {
        cout << " [";
        for (int j=0; j<k; j++) {
            cout << A[i][j] << ", ";
        }
        cout << "\b\b], ";
    }
    cout << "\b\b ]" << endl;
}

void compute (int A[][k], int G[][4])
{
    for (int i=0; i<n-1; i++)
    {
        G[i][0] = gain(A[i][0], i+1, i+2) + gain(A[i+1][0], i+2, i+1);
        G[i][1] = gain(A[i][0], i+1, i+2) + gain(A[i+1][1], i+2, i+1);
        G[i][2] = gain(A[i][1], i+1, i+2) + gain(A[i+1][0], i+2, i+1);
        G[i][3] = gain(A[i][1], i+1, i+2) + gain(A[i+1][1], i+2, i+1);
    }
}

int main()
{
    int A[n][k];
    int G[n-1][k*k];

    // construct initial configuration
    for (int i=0; i<n; i++)
        for (int j=0; j<k; j++)
            A[i][j] = n-i;

    print_config(A);

    int num_swaps = 0;
    int r, c;
    int max_gain;

    do {
        compute (A, G);

        // which swap has high info gain
        max_gain = -1;
        for (int i=0; i<n-1; i++)
            for (int j=0; j<k*k; j++)
                if (G[i][j] > max_gain) {
                   r = i;
                   c = j;
                   max_gain = G[i][j];
                }

        // Did we gain more information. If not terminate
        if (max_gain < 0) break;

        switch (c)
        {
            case 0: swap(A[r][0], A[r+1][0]); break;
            case 1: swap(A[r][0], A[r+1][1]); break;
            case 2: swap(A[r][1], A[r+1][0]); break;
            case 3: swap(A[r][1], A[r+1][1]); break;
        }

        print_config(A);
        num_swaps++;

    } while (1);
    cout << "Number of swaps is " << num_swaps << endl;
}

我针对案例 n=1,2,... 和 7 运行了上面的代码。这里分别是答案(交换次数):0、2、5、10、15、23(非常接近)和31. 我认为函数 gain() 在 n 为偶数时不能正常工作。您能否通过验证 n = 7 时的交换次数来确认这一点。等式的下限是 31，因此这是 n = 7 时的最佳交换次数。

我在此处打印 n = 5 时的输出(因为您正在寻找模式):

[ [5, 5],  [4, 4],  [3, 3],  [2, 2],  [1, 1] ]
[ [4, 5],  [5, 4],  [3, 3],  [2, 2],  [1, 1] ]
[ [4, 5],  [3, 4],  [5, 3],  [2, 2],  [1, 1] ]
[ [4, 5],  [3, 4],  [2, 3],  [5, 2],  [1, 1] ]
[ [4, 5],  [3, 4],  [2, 3],  [1, 2],  [5, 1] ]
[ [4, 3],  [5, 4],  [2, 3],  [1, 2],  [5, 1] ]
[ [4, 3],  [2, 4],  [5, 3],  [1, 2],  [5, 1] ]
[ [4, 3],  [2, 4],  [1, 3],  [5, 2],  [5, 1] ]
[ [4, 3],  [2, 4],  [1, 3],  [1, 2],  [5, 5] ]
[ [4, 3],  [2, 1],  [4, 3],  [1, 2],  [5, 5] ]
[ [1, 3],  [2, 4],  [4, 3],  [1, 2],  [5, 5] ]
[ [1, 3],  [2, 4],  [1, 3],  [4, 2],  [5, 5] ]
[ [1, 3],  [2, 1],  [4, 3],  [4, 2],  [5, 5] ]
[ [1, 1],  [2, 3],  [4, 3],  [4, 2],  [5, 5] ]
[ [1, 1],  [2, 3],  [2, 3],  [4, 4],  [5, 5] ]
[ [1, 1],  [2, 2],  [3, 3],  [4, 4],  [5, 5] ]