Stable positive/negative separation

Question

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.

Answer 1

Perl, 26 chars

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

grep($_<0,@_),grep$_>=0,@_

Answer 2

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.

Answer 3

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);}});}

Answer 4

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.

Answer 5

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.