Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

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++;
}
like image 549
Aron Woost Avatar asked Nov 05 '22 15:11

Aron Woost


2 Answers

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.

like image 84
tvanfosson Avatar answered Nov 13 '22 22:11

tvanfosson


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.

like image 42
dirkgently Avatar answered Nov 13 '22 22:11

dirkgently