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

Question

修复正整数n 和k。

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

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

适用于 n=5 和 k=2 code>，这是

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

目标是通过交换相邻数组中的数字来对这个数组进行冒泡排序（例如将 A[i][j1] 与 A[i+1][j2 ]) 直到每个条目对于每个 i，A[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 案例的更多信息。对于一般情况的任何想法就更好了。

编辑：如果我不能按照您的喜好激发这个问题，我很抱歉，但这里有一个尝试：对排列进行排序所需的冒泡排序数量是组合学和数论中非常重要的统计量，称为排列的反转数。您可以使用更好的算法对无序排列进行排序，但这就是给您代数意义的算法。如果这没有帮助，也许这个相关的帖子可能： 什么是泡沫排序有什么好处？

---

更新：下面最旧的答案给出交换次数的下限（和上限）。 第二个最旧的答案 给出了一个非常接近这个下限（通常达到它）的算法。如果有人可以改进界限，或者更好的是证明下面给出的算法是最优的，那就太棒了。

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。我认为当 n 为偶数时，函数 Gain() 不能很好地工作。您能否通过验证 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] ]

Answer 2

我知道回答自己的问题相当俗气，但我刚刚弄清楚这一点，它更接近于答案而不是问题的一部分。然而，这不是一个完整的答案，不会被接受，所以如果有人可以改进这个答案，请发表想法。

k=2 的最小交换次数（例如 m）受以下限制：

2 * (n choose 2) >= m >= (2n choose 2) / 3

为什么会这样？

上限对数组的第一个元素进行冒泡排序，然后对数组的第二个元素进行冒泡排序。这部分并不那么棘手。

下限有点棘手，但我是这样得出的。让我们来计算一下通过的次数，当较大的数字从较小的数字的左侧移动到该数字的右侧时，就会发生通过。这可能发生在 a 和 b 1 次交换中，其中 a 较大并且位于 b 左侧的数组中>。如果在一次交换中将 a 移动到带有 b 的数组，然后在以后的交换中继续移动，则也可能需要 2 次交换。为了正确地记录事情，在这种情况下，将传球数分成两半。为了使计数更容易，当两个相同的数字分开然后重新组合时，也算一次通过。

数组在 (2n select 2) 传递后完全排序，因此唯一的问题是一次交换可以发生多少次传递。下面是一个交换 a 和 c 的简单示例：

... [a,b] , [c,d] ... 
... [c,b] , [a,d] ... 

现在让我们计算可能发生的最大传递次数：

• 由于 a > c，我们肯定获得 1 个完整通过。
• 如果 a > b，那么我们得到 1/2 通过，因为 a 一定在某个时刻离开了 b。
• 如果 a > d，那么我们就得到 1/2 pass，因为 a 在某个时刻将位于 d 的右侧。
• 如果 c < d，那么我们得到 1/2 通过，因为 d 一定在某个时刻离开了 c。
• 如果 c < b，然后我们得到 1/2 通过，因为 b 在某个时刻将位于 c 的右侧。

因此，在交换中你能做的最好的事情就是获得 3 次传球（1 次全传球和 4 次半传球）。

为什么这不是一个完整的答案？

我不知道下限是否总是可以达到的！我不这么认为，而且，尽管多次尝试失败，我还是无法编写出实现它的算法。

Answer 3

这是我想到的一个直观的算法。它给出了我认为的最佳解决方案的建设性证明。

这是算法：

我尝试了 n= 4 5 6 7 9，它给出了与 badawi 相同的结果：

想法如下：

1：选择一个不在他最终位置的极值（从 1 或 n 开始）

2：找到最接近他最终位置的极值（在下面的示例中用箭头标记）

<强>3：
如果它是最大的元素，

则将其移动到另一侧并将该对中的所有最小元素向左移动，

否则

将其移动到另一侧并将每对中的所有最大元素向右移动。

注意：移位相当于用每对的较小（或最大）元素“冒泡”该值。

4：返回第 2 步，但如果您选择了其中一个大的，则选择其中一个小的，反之亦然。

它非常直观并且似乎有效：

示例 n=5：

11 22 33 44 55 
^
|
12 23 34 45 51 (4 moves) // shifted all larger numbers to the left
          ^
          |
52 13 24 43 51 (3 moves) // shifted all smaller numbers to the right
   ^
   |
52 34 24 35 11 (3 moves) // shifted all larger numbers to the left
          ^
          |
55 24 34 32 11 (3 moves) // smaller to the right
   ^
   |
55 44  33 22 11 (2 moves) // larger to left

总共 15 步。

第二个例子 n=7:

11 22 33 44 55 66 77 // 6 moves
 ^
12 23 34 45 56 67 71 //5 moves
                ^
72 13 24 35 46 56 71 //5 moves
   ^
72 34 25 36 46 57 11 // 4 moves
                ^
77 24 35 26 36 45 11 //4 moves
   ^
77 45 36 26 35 42 11 //1 move
       ^       
77 65 34 26 35 42 11 //2 moves
         ^
77 65 34 56 34 22 11 //2 moves
          ^
77 66 54 53 34 22 11 //1 move
          ^
77 66 54 45 33 22 11 //1 move
          ^
77 66 55 44 33 22 11

总数: 31

如果我不清楚，请随时问我问题。

用手做起来非常容易。你可以自己用 6 或 7 尝试一下或者编写一个算法。

我用 6 试了一下，结果是 23。
，如果是 7，则为 31，如果为 9，则为 53，手动计算需要一分钟，而无需计算任何内容

为什么这个解决方案是最佳的：

每次将一个大元素移动到另一侧时，您将这对中所有最小的一个移到左侧。

因此，移动所有大元素不会使您失去移动所有最小元素的任何移动。

你总是向“正确的方向”移动你的元素，

此外，为了移动极端的元素，你需要最少的移动次数。
（这是因为算法采用最接近他最后位置的极值，不会丢失任何移动）

对于小元素的推理是相同的。

该算法为您提供最佳移动，因为它不会做出任何操作
不必要的举动。

希望我没有犯任何错误。

它证明 badawi 结果如您所料是最佳的。