GATE CS 1999 Q1.13 — Asymptotic Worst Case Time and Space Complexity

To find the minimum number of exchanges required in the worst case to partition an array of $n$ numbers such that all negative values appear before all positive ones, we can analyze the problem as follows:

1. Let $n_-$ be the number of negative elements and $n_+$ be the number of positive elements in the array, so that $n_- + n_+ = n$.
2. In the partitioned array, the first $n_-$ positions must contain all the negative elements, and the remaining $n_+$ positions must contain all the positive elements.
3. Suppose there are $k$ positive elements currently located in the first $n_-$ positions. This means there are exactly $n_- - k$ negative elements in this region.
4. Since the total number of negative elements is $n_-$, the number of negative elements located in the second region (the last $n_+$ positions) must be: $$n_- - (n_- - k) = k$$
5. To partition the array, we only need to swap each of the $k$ misplaced positive elements in the first region with a misplaced negative element in the second region. This requires exactly $k$ exchanges.
6. The worst-case scenario occurs when the number of misplaced elements $k$ is maximized. Since $k \le n_-$ and $k \le n_+$, we have: $$k \le \min(n_-, n_+)$$
7. Subject to $n_- + n_+ = n$, the maximum possible value of $\min(n_-, n_+)$ is $\lfloor n/2 \rfloor$.

Thus, the minimum number of exchanges required in the worst case is $\lfloor n/2 \rfloor$. Since this value is not represented by options A, B, or C, the correct option is D.