Edit Question - KnowledgeHub

Title Body

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

Tags (comma-separated) Cancel