Ordering of a 2D array

I am trying to solve a problem on 2D arrays and need little help. The problem goes like this:

Suppose we have a 2D array A of size nxn comprising of unique elements. The need to rearrange the elements of A as follows. Let A11, A12, A21, A22 be f开发者_StackOverflowour mutually disjoint subarrays of A, each of size n/2 x n/2. Then A11 < A12 < A21 < A22. If each of these subarrays is recursively split into four equal-sized sub-arrays, then also the property holds.

User input: n, N (≥ n2). n is a power of 2

I have tried many things but nothing seems to work.

You need to create a function which will convert an index between 0 and n*n-1 to coordinates in your array according to the ordering in question. Then you just run some usual 1D sorting algorithm, on an array of size n*n, jth element of which is substituted using that function. It solves the problem.

Update: the mapping function maps numbers in this matrix to their coordinates:

 0  1  4  5
 2  3  6  7
 8  9 12 13
10 11 14 15

Piggybacking somewhat on the answer of unkulunkulu I think you could approach it as follows:

Take all the values in your matrix (2D) and put them in a simple array (1D). Then take this array and sort the values from lowest to highest.

Now what you need to do is fill the matrix again but in such a way that it conforms to the rules you have specified. If you have a look at a Z-order space filling curve in 2D, you will find that if you fill you matrix in this order (with the sorted elements), that the resulting matrix has your desired properties.

Now actually coding this would be up to you.

The book numerical recipes chapter 21.8 http://www.nrbook.com/nr3/ gives an analytic expression to calculate an index into the 2D array given the coordinates of a quadtree.

Here is another straight forward approach that I tried, but I don't like it as much:

(defun quad-pos (pos)
  "POS is a list of letters that indicate the position in a 2x2 matrix [a,b; c,d]."
  (let ((x 0)
    (y 0)
    (s 1))
    (dolist (e pos)
      (setf s (/ s 2))
      (ecase e
    ('a )
    ('b (incf x s))
    ('c (incf y s))
    ('d (incf x s) (incf y s))))
    (values x y)))
#+nil
(quad-pos '(a)) ;=> 0, 0
#+nil
(quad-pos '(a b c)) ;=> 1/4, 1/8
#+nil
(quad-pos '(d d d d)) ;=> 15/16, 15/16