Optimal bubble sorting algorithm for an array of arrays of numbers -

fix positive integers n , k.

let a array of length n a[i] array of length k every entry n-i. example, n=5 , k=1, just

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

and n=5 , k=2, is

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

the goal bubble sort array of arrays swapping numbers in adjacent arrays (e.g. swap a[i][j1] a[i+1][j2]) until every entry of a[i] i+1 every i.

the question is: how many swaps necessary , what's optimal algorithm?

note: there many, many better sorting algorithms use. however, question, interested in applying bubble sort described above. can interchange entries adjacent arrays, , interested in minimum number of such interchanges necessary. appreciate suggestions other sorting algorithms, problem trying understand.

examples:

for k=1, known. number of swaps inversion number of a regarded permutation, , minimum number of swaps binomial coefficient (n choose 2) = n(n-1)/2 , can attained swapping out of order pair: a[i] > a[j]. first example, here's 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 same strategy give bound of 2 (n choose 2) swaps needed. example above, means 20 swaps. there solution uses 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 optimal n=5 , k=2 (proof brute force find solutions). n=6, best solution takes 22 swaps, solution doesn't nice 1 n=5 (follow 5 right, 1 left, 5 right, etc), still don't know optimal strategy, less formula or better bound number of swaps.

i've been thinking couple of days , haven't come enlightening. if has thoughts on problem, please share them. i'd thrilled knowing more k=2 case. better thoughts on general case.

edit: apologize if cannot motivate problem liking, here's attempt: number of bubble sorts needed sort permutation important statistic in combinatorics , number theory, called inversion number of permutation. can sort out of order permutation using better algorithms, 1 gives algebraic meaning. if doesn't help, perhaps related post may: what bubble sort for?

---

update: oldest answer below gives lower (and upper) bound number of swaps. second oldest answer gives algorithm comes close lower bound (often attaining it). fantastic if improve bound, or, better, prove algorithm given below optimal.

this not optimal answer, share attempt may improve it. did not thought finding formula calculate minimum number of swaps rather on optimal algorithm. algorithm based on k = 2.

the basic idea based on information gain. let assume = {[i,j] : 1<=i<=n, 1<=j<=n} represents configuration. in each step, have 4 * (n-1) possible swapping move 1 configuration configuration. example if n = 2 (i.e. = [ {2,2}, {1,1} ] ), have 4 possible swapping a[0][0] <-> a[1][0], a[0][0] <-> a[1][1], a[0][1] <-> a[1][0], , a[0][1] <-> a[1][1]. thus, our objective select swap has high information gain when need move 1 configuration configuration.

the tricky part "how calculate information gain". in solution (below), information gain based on distance of value correct position. let me show code (written in c++) understand trying 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 - item ; }  void swap(int &x, int &y) {     int temp = x;     x = y;     y = temp; }  void print_config (int a[][k]) {     cout << "[";     (int i=0; i<n; i++) {         cout << " [";         (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]) {     (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     (int i=0; i<n; i++)         (int j=0; j<k; j++)             a[i][j] = n-i;      print_config(a);      int num_swaps = 0;     int r, c;     int max_gain;      {         compute (a, g);          // swap has high info gain         max_gain = -1;         (int i=0; i<n-1; i++)             (int j=0; j<k*k; j++)                 if (g[i][j] > max_gain) {                    r = i;                    c = j;                    max_gain = g[i][j];                 }          // did 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 " << num_swaps << endl; } 

i ran above code cases n=1,2,... , 7. here answers (number of swaps) respectively: 0, 2, 5, 10, 15, 23 (very close), , 31. think function gain() not work when n even. can confirm validating number of swaps when n = 7. lower bound of equation 31 optimal number of swaps when n = 7.

i printing here output when n = 5 (since looking 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] ]