Stable positive/negative separation

From SO.

You are given an array with positive and negative integers. Write a function to change the elements order in the array such that negative integers are at the beginning, the positive integers are at the end and two integers that have the same sign don't change order.

Example:

• Input 1,7,-5,9,-12,15
• Output -5,-12,1,7,9,15
• Input 1,-2,-1,2
• Output -2, -1, 1, 2

Constraints: O(n) time limit and O(1) extra memory.

-
@Alexandru Deleted my answer. I've misread the specifications :) – belisarius Feb 4 '11 at 15:14
O(1) extra memory makes it impossible to solve in languages without mutable data structures (and unwieldy to solve in languages which default to immutable data structures) :-( – sepp2k Feb 4 '11 at 15:42
@sepp2k. I know, but without O(1) extra memory it is too easy. – Alexandru Feb 4 '11 at 15:43
Is it at all possible in O(1) memory? The SO people haven't found one yet. – J B Feb 5 '11 at 5:46
This question doesn't mention anything about being a code golf, yet the answers are all golfing. Can you clarify this? If it was intended to be code golf, this shows people are not specifying properly and that is a problem. If it was not, then answerers are not looking at the lack of the shortest code constraint and that is also a problem. – marcog Feb 5 '11 at 12:15

Perl, 26 chars

Use where you'd use a list. Input in `@_`. (hence could also be wrapped in a `sub`)

``````grep(\$_<0,@_),grep\$_>=0,@_
``````
-
This doesn't qualify. I uses more than O(1) extra memory. And is not a function. – Alexandru Feb 4 '11 at 15:12
Indeed. Back to the drawing board. – J B Feb 4 '11 at 15:37

Mathematica 26 chars

.

``````Sort[#, Sign@#1 <= Sign@#2 &] &
``````

It's stable:

``````Sort[#, Sign@#1 <= Sign@#2 &] &@{10, 11, -100, -2, -3, 7}
{-100, -2, -3, 10, 11, 7}
``````

Edit

Linearity test

``````k = {};
For[i = 1000, i < 20000, i += 500,
j = Table[RandomInteger[i] (-1)^(RandomInteger[{0, 1}]), {i}];
AppendTo[k, {i, Length@Trace[Sort[#, Sign@#1 <= Sign@#2 &] &@j]}];
];
Show[ListPlot[k, PlotStyle -> Red], Plot[{line}, {x, 1000, 20000}]]
``````

It's not true sorting, just swapping.

-
Does this preserve the order of negative/positive integers? – Alexandru Feb 4 '11 at 15:10
This does almost certainly not have running time in O(n). – sepp2k Feb 4 '11 at 16:02
@sepp2k See edit – belisarius Feb 4 '11 at 17:27
@belisarius. I'm not sure about a couple of things. 1) Implementation of Sort in Mathematica (Does it use O(1) memory?). 2) Your linearity test. It may be that it works only when there are 50/50 negatives/positives. – Alexandru Feb 4 '11 at 19:43
@Alexandru The linearity test is OK. Verified with several distributions. However, the memory is O(n), as it constructs the list for output in a new area. Good point. – belisarius Feb 4 '11 at 20:54
show 1 more comment

Java 147 characters (not yet tested):

``````void f(List<Integer> l){Collections.sort(l,new Comparator<Integer>(){public int compare(Integer a,Integer b){return a<0?(b<0?0:1):(b<0?-1:0);}});}
``````
-
I don't know Java, but that Collections.sort smells very `O(n log n)` – J B Feb 4 '11 at 14:47
I know Java and that Collections.sort is very `O(n log n)` – sepp2k Feb 4 '11 at 15:53
Whoops, I forgot about the O(n) time constraint. Let me know if I should remove this answer... – Daniel Feb 6 '11 at 14:57

Python (99)

``````def C(a):
A=-1;b=len(a)-1
while b>A:
if a[b]<0:a=[a[b]]+a;a.pop(b+1);A+=1;b+=1
b-=1
return a
``````

Not too much of a challenge. Input is given like `[a, b, c, d, e, ....]`. When it finds a negative number, it moves the number to the front of the list.

-
 Are you sure this is O(n)? Doesn't look it to me. – Peter Taylor Jul 1 '12 at 19:13 I ran it with some RNG'd lists, for all cases up to 100 it ran for `n-1` iterations. – beary605 Jul 2 '12 at 4:03 Is `a.pop(b+1)` constant time? (Also, the spec requires a stable sort, and this isn't. E.g. the output of `C([-3, 3, -2, 2, -1, 1])` is not `[-3, -2, -1, 3, 2, 1]` as required). – Peter Taylor Jul 2 '12 at 6:53 I'm pretty sure `a.pop(b+1)` is the same as `del a[b+1]`, which is most likely constant time. I've fixed the code. – beary605 Jul 2 '12 at 7:21

K, 18

``````{(x@&a),x@&~a:x<0}
``````

As for time/memory, I don't really know how to calculate it so feel free to disregard the answer if necessary.

-