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!
anatolyg :
I didn't understand how exactly you want to reorder the elements\n\n\n row-wise, monotonically for the hue, and then column-wise for the diameter, monotonically\n\n\nbut here are some ideas you might be able to use.\n\n\nYour 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).\nYour 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.\nOne 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)\n",
2013-06-22T13:19:40
user1589069 :
I see.\nI suppose such a diamond shape could be directly represented by an array.\nIgnore all the -1 entries. \n\n{ row-0 row-1 row-2 row-3 ... row-13 }\n\n{ 1 2 2 2 3 3 3 3 3 4 4 4 5 }\n\n\nYou can now sort the array as you like.\nSort it twice, once for hue, once for diameter; or figure out how to sort an array by two criteria. \n\nYou can also work in-place, if you just write a function for converting an array index to diamond-coordinates. With that done, you can just work on the diamond-structure as if it was an array. ",
2013-06-22T07:54:24