Partition array - elements non-negative and negative. Minimal number of replacements of elements I consider following problem:
It is given array with numbers, for example $[-2,0,1,-324,213,321,-2]$.
The problem is: replace elements such that negative numbers precede the non-negative. For our example: $[-2, -324, -2, 321,0,213,1]$.
Additional requirement is that algorithm should do minimal number of replacements.   

My approach
Let's use partition from qsort algorithm - pivot is always $0$. It does $\lfloor n/2\rfloor $ replacements.
I think that it is minimal number. It is because of pesimistic case:
$|[1,1,..,1,-1,-1,...-1]|=n$  - in this case we must do at least $\lfloor n/2\rfloor $ replacements.   

Can you give me algorithm that do less than $\lfloor n/2\rfloor$ replacements ?
Hint: 

Create a new array $B=[]$ where $B[i]=1$ if  $A[i]&lt;0$ and $2$ elsewhere.
You can prove that sorting $B$ is same as performing said operation on $A$

So now, We have to sort an array which only contains two values.
You can do this by a greedy algorithm, whose proof you can obtain by the principle of Induction.

As an extra hint: Let $B=[1.....1,2.....2,1,........]$. where  C is another segment of the array. You have to do something now.

Trust me this is great help. You can continue from here.

As for why it requires fewer(or equal) than $n/2$. The proof is quite easy, once you've devised the algorithm.