1
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ I think there's some confusion in the question: just because there is one input array where you need to do $\ge n/2$ replacements doesn't necessarily mean that $\ge n/2$ replacements are needed on all input arrays, or that partition from qsort gives the correct answer for all possible input arrays. "minimal number of replacements" would normally be interpreted as "the minimum number of replacements that are necessary for this particular input". $\endgroup$ – D.W. Nov 5 '15 at 23:06
2
$\begingroup$

Hint:

Create a new array $B=[]$ where $B[i]=1$ if $A[i]<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.

$\endgroup$
  • $\begingroup$ Algorithm sholud work in situ (in place) $\endgroup$ – user40545 Nov 5 '15 at 23:53
  • $\begingroup$ I don't undersand. After all, partition from qsort do not more than $n/2$ replacements. Where am I wrong ? $\endgroup$ – user40545 Nov 6 '15 at 0:01
  • 1
    $\begingroup$ You can apply the same algorithm for $B$ to solve the problem in A in place. When you find the correct algorithm, you will see it for yourself. For the moment stick to solving $B$ which you may find easier to solve $\endgroup$ – jjohn Nov 6 '15 at 0:01
  • $\begingroup$ Ok, tell me once again: What algorithm should I think firstly ? $\endgroup$ – user40545 Nov 6 '15 at 0:15
  • 1
    $\begingroup$ Try the $B$ problem. Give it some thought and if you cannot find something. Ask again. But think and try first! You won't learn otherwise! $\endgroup$ – jjohn Nov 6 '15 at 0:45

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.