Suppose we want to arrange the n numbers stored in an array such that all…
1999
Suppose we want to arrange the n numbers stored in an array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is:
- A.
n - 1
- B.
n
- C.
n + 1
- D.
None of the above
Attempted by 51 students.
Show answer & explanation
Correct answer: D
The correct answer is: None of the above.
To make all negative values appear before all positive values, use two pointers: one from the left to find a misplaced positive value and one from the right to find a misplaced negative value. One exchange swaps these two misplaced elements and fixes one element on each side of the partition.
The worst case occurs when all positive values are in the first part and all negative values are in the second part. Then the number of required exchanges is at most floor(n/2), because each exchange fixes a pair of misplaced elements.
Since floor(n/2) is not equal to n - 1, n, or n + 1, the correct option is None of the above.