Diamond array sorting in C

Question

I have the following homework assignment in C. I basically need an approach rather than a solution.

We have a 13 x 13 array. In the array, we have a diamond shape that we need to consider. Everything outside this diamond is initialized to -1 (unimportant). Example 5 x 5 array below-

x x 1 x x 
x 2 2 2 x
3 3 3 3 3
x 4 4 4 x
x x 5 x x

x=-1

Now in this array, the values we have in the diamond for each entry contains 11 bits. 5 lsb contains one data (hue), and other 6 contains another data (diameter). We need to sort the data row-wise, monotonically for the hue, and then column-wise for the diameter, monotonically.

What would be the most efficient and memory conserving way of doing this? Since we need to conserve this, it's best if the entries are swapped around rather than creating another array. In the end, we will end up with a sorted diamond array (still with the -1s). Thanks a lot in advance guys!

Answer 1

I didn't understand how exactly you want to reorder the elements

row-wise, monotonically for the hue, and then column-wise for the diameter, monotonically

but here are some ideas you might be able to use.

• Your array is 13x13 (169 elements); out of that, almost exactly half (84) are empty, so you can use them as temporary storage (for e.g. radix-sort).
• Your values have 11 meaningful bits; numbers in real computers have either 16 or 32 bits - so you can use the 5 (or 21, depending on your system) most significant bits as temporary storage.
• One possibly good way to use the upper 5 bits is putting a copy of the 5 LSB (hue) there. This will reverse the significance of the two parts when doing normal integer comparison (making hue more significant than diameter)