Optimal bubble sorting algorithm for an array of arrays of numbers

Question

Fix positive integers n and k.

Let A be an array of length n with A[i] an array of length k where every entry is n-i. For example, with n=5 and k=1, this is just

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

and for n=5 and k=2, this is

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

The goal is to bubble sort this array of arrays by swapping numbers in adjacent arrays (e.g. swap A[i][j1] with A[i+1][j2]) until every entry of A[i] is i+1 for every i.

The question is: how many swaps are necessary and what's an optimal algorithm?

NOTE: There are many, many better sorting algorithms to use. However, for this question, I am only interested in applying a bubble sort as described above. I can only interchange entries from adjacent arrays, and I am only interested in the minimum number of such interchanges necessary. I do appreciate all the suggestions for other sorting algorithms, but this is the problem that I am trying to understand.

EXAMPLES:

For k=1, this is well known. The number of swaps is the inversion number of A regarded as a permutation, and so the minimum number of swaps is the binomial coefficient (n choose 2) = n(n-1)/2 and this can be attained by swapping any out of order pair: A[i] > A[j]. For the first example, here's an optimal bubble sort:

[ [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] ]

For k=2, using the same strategy would give a bound of 2 (n choose 2) swaps needed. For the example above, that means 20 swaps. But there is a solution that uses only 15 swaps:

[ [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] ]

This solution is optimal for n=5 and k=2 (proof by brute force to find all solutions). For n=6, the best solution takes 22 swaps, but the solution doesn't look as nice as the one for n=5 (follow the 5 right, then the 1 left, then the 5 right, etc), so I still don't know an optimal strategy, much less a formula or better bound for the number of swaps.

I've been thinking about this for a couple of days now and haven't come up with anything enlightening. If anyone has any thoughts on this problem, then please share them. I'd be thrilled with knowing more about the k=2 case. Even better for any thoughts on the general case.

EDIT: I apologize if I cannot motivate this problem to your liking, but here's an attempt: the number of bubble sorts needed to sort a permutation is a very important statistic in combinatorics and number theory, called the inversion number of the permutation. You can sort an out of order permutation using much better algorithms, but this is the one that gives you the algebraic meaning. If that doesn't help, perhaps this related SO post may: What is a bubble sort good for?

---

UPDATE: The oldest answer below gives a lower (and upper) bound for the number of swaps. The second oldest answer gives an algorithm that comes really close to this lower bound (often attaining it). It would be fantastic if someone could improve the bound, or, even better, prove that the algorithm given below is optimal.

Answer 1

This is not an optimal answer, but i would like to share my attempt as someone may improve it. I did not thought about finding a formula to calculate the minimum number of swaps but rather on the optimal algorithm. The algorithm is based on k = 2.

The basic idea is based on information gain. Let us assume that A = {[i,j] : 1<=i<=n, 1<=j<=n} represents a configuration. In each step, we have 4 * (n-1) possible swapping to move from one configuration to another configuration. For example if n = 2 (i.e. A = [ {2,2}, {1,1} ] ), then we have 4 possible swapping A[0][0] <-> A[1][0], A[0][0] <-> A[1][1], A[0][1] <-> A[1][0], and A[0][1] <-> A[1][1]. Thus, our objective is to select the swap that has high information gain when we need to move from one configuration to another configuration.

The tricky part will be "how to calculate the information gain". In my solution (below), the information gain is based on the distance of a value from its correct position. Let me show you my code (written in C++) to understand what i am trying to say:

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;
}

I ran the above code for cases n=1,2,... and 7. Here are the answers (number of swaps) respectively: 0, 2, 5, 10, 15, 23 (very close), and 31. I think that the function gain() does not work well when n is even. Can you confirm that by validating the number of swaps when n = 7. The lower bound of your equation is 31 so this is the optimal number of swaps when n = 7.

I am printing here the output when n = 5 (since you are looking for a pattern):

[ [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] ]