Minimum number of exchanges

Question

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 ?

I tried it in the following way :

the worst case would be when we have the positives and negatives arranged in an alternate fashion. So, minimum number of exchanges could be (n/2) + (n-2)/2 + (n-4)/2 + ....

here, I am getting confused regarding calculating this sum. after first series of exchanges we could eliminate the last two and then left with n-2 numbers.

Can someone help me out ?

Answer 1

Here's my vision.

Suppose you have $n_1$ of negative numbers. Then, after the procedure you must have all of the $[1..n_1]$ numbers negative. So, the number of operations is $n_1 - h_1$, where $h_1$ is the number of negative elements already in $[1..n_1]$. The same goes about positive numbers - we can place them at the end of the array with $n_2 - h_2$ operation (I believe you can see what the notation mean).

The overall number of operations is $min(n_1 - h_1, n_2 - h_2)$

It's not difficult to see, that the value of the minimum is $n/2$.

Answer 2

You define optimum for an algorithm in terms of number of swaps.

A swap can at most move 2 items into the correct place.

If a list is not in order, then there exist at least two items out of place. Therefore there exists an algorithm which puts 2 items into the correct place with each swap.

There exists a worst for the optimal algorithm case which has every item out of place: $\frac N 2$ positive values followed by $\frac N 2$ negative values.

There for the worst case number of swaps is $\frac N 2$.

Answer 3

Here is an algorithm for the minimal number of swaps.

1. Count the number of negatives in the array. Let this number be $m$.
2. Swap any positives in positions $[1,\ldots,m]$ with negatives in positions $[m+1,\ldots,n]$.

Since each swap ensures two positions in the array are correct, at most $\frac{n}{2}$ swaps are needed to ensure all positions are correct.