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 ?

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

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.

| cite | improve this answer | |
  • $\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$ – Yuval Filmus Mar 15 '14 at 2:58

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.

| cite | improve this answer | |
  • $\begingroup$ It's clearly possible to do this with $O(n)$ exchanges so sorting can't be the answer. $\endgroup$ – David Richerby Dec 15 '13 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$ – user1548346 Dec 15 '13 at 19:09
  • 1
    $\begingroup$ I think this answer is supposed to be: perform a Quicksort partitioning with pivot $0$. $\endgroup$ – Raphael Mar 14 '14 at 21:00
  • $\begingroup$ I agree with Raphael. However this implies the "analysis" is off, since a single partitioning is $\Theta(n)$. $\endgroup$ – FrankW Mar 14 '14 at 21:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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