Formula needed: Sort array to array-"zig-zag"

Question

I have the following array:

a = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]

I use it for some visual stuff like this:

1   2  3  4

5   6  7  8

9  10 11 12

13 14 15 16

Now I want to sort the array like this to have a "zig-zag" when rendering later.

// rearrange the array according to this schema
1  3  6 10

2  5  9 13

4  8 12 15

7 11 14 16

// the original array should look like this:

a = [1,5,2,9,6,3,13,10,7,4,14,11,8,15,12,16]
// the second index to draw should be the first index in the second row,
// which is represent by 5 in the original 1D Array

Yeah, now I'm looking for a smart formula to do that

ticker = 0;
rows = 4; // can be n
cols = 4; // can be n
originalArray = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16];
newArray = [];

while(ticker < originalArray.length)
{
    //do the magic here
    ticker++;
}

Answer 1

You can leave it sorted in the original order, you just have to step through it differently. EDIT: Turns out that my naive implementation didn't account for the differing step size based on the diagonal. The code below does and has been tested in C#.

 var diagonals = new [] { 1, 2, 3, 4, 4, 3, 2, 1 };
 for (int i = 0, m = 0; m < 4; i = i + m, ++m) {
     for (int j = m, k = 0; k < 4; j = j + diagonals[m+k+1], ++k) {
          Console.Write( i+j+1  );
          Console.Write( " " );
     }
    Console.WriteLine();
 }

Obviously, you could use this algorithm to fill a new array if you needed to keep that ordering around. It should also scale -- you just need to change the termination conditions to the square root of the array size and automate the generation of the diagonals.

Answer 2

Look at the structure of your matrix:

1    3
|  / /
| / / 
|/ /  ...
2 /  5 
 / /    
/ /
4

The 1st row starts at 1

The 2nd row starts at 2 = 1 + 1 (# elements in 1st zig)

The 3rd row starts at 4 = 1 + 1 (# elements in 1st zig) + 2 (# elements in 2nd zig)

...

The 3rd row ends at 6 = start of 3rd row + row num = 4 + 3 = 7

You can derive a closed form formula for the ith row and go ahead.