As fast as possible, preserving the sequence without using sorting and another array. Initially, there are no zero elements in the array.

Closed due to the fact that off-topic participants Modus , user192664, aleksandr barakin , 0xdb , Dmitry Kozlov 20 Nov '18 at 12:01 .

It seems that this question does not correspond to the subject of the site. Those who voted to close it indicated the following reason:

  • " Learning tasks are allowed as questions only on the condition that you tried to solve them yourself before asking a question . Please edit the question and indicate what caused you difficulties in solving the problem. For example, give the code you wrote, trying to solve the problem "- Modus, Community Spirit, aleksandr barakin, 0xdb, Dmitry Kozlov
If the question can be reformulated according to the rules set out in the certificate , edit it .

1 answer 1

Enter two indices - the first element and the last.

We go from the first forward until the indices do not intersect.

If the first is positive, leave it in place. If negative - look at the second index. If there is a positive element, swap them and shift the indices. If negative - go to the second index to the beginning before the first positive element, where we perform the exchange. Unless this positive is to the left of a smaller index, then everything is done, the work is done.

Like that. Fast, O (n). Type Code

for(int begin = 0, end = /* Последний индекс */; begin < end; ++begin) { if (a[begin] < 0) { while(end > begin && a[end] <= 0) --end; if (a[end] > 0) { int tmp = a[begin]; a[begin] = a[end]; a[end] = tmp; --end; } } }
  • All, of course, brilliant. But is it possible so that the order is preserved? - Grigoriy
  • Can. But this is a kick in one place, that tasks must be given EXACTLY . This solution corresponds exactly to your question. "Give water to drink, otherwise you want to eat, and there is nowhere to spend the night." - Harry