1
$\begingroup$

Suppose we want to arrange n numbers stored in an array such that all negative value occur before the positive ones. What will be the minimum number of exchanges in the worst case ?

$\endgroup$
1
  • 2
    $\begingroup$ Using which algorithm? Asking for a worst-case does not make sense without fixing the algorithm $\endgroup$
    – Raphael
    Commented Mar 14, 2014 at 21:00

2 Answers 2

4
$\begingroup$

You can keep a pointer to the currently first positive value in the list, which initializes to 0. Then scan through the list, when you see a negative value swap it with the positive value, and increment your pointer.

You get O(n) swaps in the worst case.

If the first half is positive and second half is negative, you have to have at least n/2 swaps, as the second half needs to swap places with the first half.

To actually get n/2 swaps, you can first count the # of positive values, and if the positive values are greater, iterate the list in reverse order, and keep a pointer first negative value in the list. You can then stop if you have swapped all the positive or negative values.

$\endgroup$
1
  • $\begingroup$ In other words, for even $n$, the answer is $n/2$, while for odd $n$, it's $(n-1)/2$. Both cases at once can be stated as $\lfloor n/2 \rfloor$. $\endgroup$ Commented Mar 15, 2014 at 2:58
-3
$\begingroup$

For your point we will use Quick sort algorithm but only for one time (one pivot) and for the worst case it will take O(nlogn) as we find solution in the first step.

$\endgroup$
4
  • $\begingroup$ It's clearly possible to do this with $O(n)$ exchanges so sorting can't be the answer. $\endgroup$ Commented Dec 15, 2013 at 19:04
  • $\begingroup$ the point which i am talking about is not to sort the list but only can take that technique of taking one index and put all small elements to the left and all large to the right. $\endgroup$ Commented Dec 15, 2013 at 19:09
  • 1
    $\begingroup$ I think this answer is supposed to be: perform a Quicksort partitioning with pivot $0$. $\endgroup$
    – Raphael
    Commented Mar 14, 2014 at 21:00
  • $\begingroup$ I agree with Raphael. However this implies the "analysis" is off, since a single partitioning is $\Theta(n)$. $\endgroup$
    – FrankW
    Commented Mar 14, 2014 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.