3. CPS: Strategy design, correctness & efficiency: Data Reordering (13 points)

Consider the three computational strategies to solve the above data reordering problem:

Strategy 1: Sort the array in the descending order.

Is this strategy correct? (Circle one) yes no

Will this strategy preserve the original relative orders of the negative, zero and positive numbers? (Circle one) yes no maybe

Strategy 2:

Scan the input array A left to right and copy all negative numbers to a new array B of the same size starting from its first index.

Then repeat the above, this time copying zeroes into B, starting with the index to the right of the last negative number copied into B.

Then repeat the above once more, this time copying positive numbers into B, starting with the index to the right of the last zero copied into B. Output array B.

Is this strategy correct? (Circle one) yes no

Will this strategy preserve the original relative orders of the negative, zero and positive numbers? (Circle one) yes no maybe

Can this strategy (as is with no modifications) be translated into an in-place algorithm? (Circle one) yes no

Can this strategy (as is with no modifications) be translated into an on-line algorithm? (Circle one) yes no

Strategy 3:

Scan the input array A, counting the number of negative, zero and positive numbers. Let these counts be x, y and z respectively.

Create a new array B of the same size and set a local variable neg to 1, zero to x+1, and pos to x+y+1.

Scan the input array from left to right, and if the current number being looked at is negative, copy it to B[neg] and increment neg, if it is a zero, copy it to B[zero] and increment zero, and if it is positive, copy it to B[pos] and increment pos.

Output array B.

Is this strategy correct? (Circle one) yes no

Will this strategy preserve the original relative orders of the negative, zero and positive numbers? (Circle one) yes no maybe

Can this strategy (as is with no modifications) be translated into an in-place algorithm? (Circle one) yes no

Can this strategy (as is with no modifications) be translated into an on-line algorithm? (Circle one) yes no

Considering the memory needed to store the input, output and any local variables, which of the two strategies strategy-1 and strategy-2 is more space-efficient? (Circle one)

strategy-2 strategy-3 both are equally space-efficient

Considering the number of basic operations executed, which of the two strategies strategy-1 and strategy-2 is more time-efficient? (Circle one)

strategy-2 strategy-3 both are equally time-efficient

Is it possible to modify strategy-3 so it can be turned into an in-place algorithm? (Circle one) yes no