CODEWITHSUNDEEP
carrayssortingparameters
bauer2010
bauer2010

Reputation: 73

Two-parameter Array Sort

I have a 14x14 array, with each element being binary-packed information that when unpacked will give me two parameters, A and B. (Let's put the parameters in the form A:B for easier discussion here.) Now, I need to sort the array such that A increases from top to bottom (column) and B increases from left to right (row).

I thought about sorting the rows by B, and then sorting the columns by A, but then I realized that won't work. Say I sort the rows by B. Then when I sort the columns by A, that could screw up the ordering of B.

Any ideas?

Upvotes: 4

Views: 243

Answers (1)

SheetJS
SheetJS

Reputation: 22905

You can sort the entire list of 196 elements by A, then lay out the elements so that the first row contains the smallest 14 A, the next row contains the next smallest, etc. In this way, every element from the ith row is smaller (according to A) than every element from the jth row if i > j.

Then, go row by row and sort by B.

As a small example, lets do a 3x3 case with pairs (9,1) (8,2) ... (1,9). The sort by A would yield (1,9) ... (9,1) which you lay out like this:

(1,9)  (2,8)  (3,7)
(4,6)  (5,5)  (6,4)
(7,3)  (8,2)  (9,1)

Then you sort each row by B. Changing the order of the elements of B doesn't break the core assumption about A because every element in a given row are less than every element in higher rows (for example, the minimum A in the third row is 7 and the maximum A in the second row is 6).

Then you get:

(3,7)  (2,8)  (1,9)
(6,4)  (5,5)  (4,6)
(9,1)  (8,2)  (7,3)

EDIT: the question was clarified as follows:

Ok, this is starting to make sense, but say I have this: [[-1 -1 2:8 -1 -1] [ -1 3:7 4:16 5:2 -1] [ 2:14 3:9 2:6 5:9 1:2] [ -1 9:8 4:2 9:1 -1] [-1 -1 2:2 -1 -1]]. "-1" represents a null value, thus should not be sorted. The final sorted array needs to remain in such a diamond shape.

To keep the "diamond shape", you merely fill out the matrix according to the pattern. With the example:

[[-1 -1 2:8 -1 -1] [ -1 3:7 4:16 5:2 -1] [ 2:14 3:9 2:6 5:9 1:2] [ -1 9:8 4:2 9:1 -1] [-1 -1 2:2 -1 -1]]

First pull out the elements

[2:8 3:7 4:16 5:2 2:14 3:9 2:6 5:9 1:2 9:8 4:2 9:1 2:2]

Then sort by A (In this case, to break ties, we use the B value):

[1:2 2:2 2:6 2:8 2:14 3:7 3:9 4:2 4:16 5:2 5:9 9:1 9:8]

Then construct the rows we need. If you look at the pattern, the number of elements in the rows are 1,3,5,3,1, so the rows are

[[1:2] [2:2 2:6 2:8] [2:14 3:7 3:9 4:2 4:16] [5:2 5:9 9:1] [9:8]]

Now we sort the rows by B value:

[[1:2] [2:2 2:6 2:8] [4:2 3:7 3:9 2:14 4:16] [9:1 5:2 5:9] [9:8]]

Now we can rebuild the diamond:

[[-1   -1   1:2  -1     -1] 
 [-1   2:2  2:6  2:8    -1] 
 [4:2  3:7  3:9  2:14 4:16] 
 [-1   9:1  5:2  5:9    -1] 
 [-1   -1   9:8  -1     -1]]

Verify that the rows and columns are correctly sorted :)

Upvotes: 5

Related Questions