Suppose we want to arrange the $n$ numbers stored in any array such that all negative values occur before all positive ones. Minimum number of exchanges required in the worst case is
@ Chhotu by that way (partition method) it wont take minimum exchanges.
Answer is (D) None of these.
We just require $n/2$ swaps in the worst case. The algorithm is as given below:
Find positive number from left side and negative number from right side and do exchange. Since, at least one of them must be less than or equal to $n/2$, there cannot be more than $n/2$ exchanges. An implementation is given below:
can I use simple selection sort instead ? coz it will too lead to a minimum of n/2 exchange.
Consider an array of elements: -6,-1,-5,-2,-4
Using selection sort(descending) there will be 4 exchanges(more than n/2), but no exchanges are required according to algorithm given here: