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.
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 ?