Ordering an array of negatives, zero and positives integers with one iteration

Question

Take an array of integers containing negative numbers, positive numbers and zeros. Group it with one iteration and in place such that all of the negative numbers come first, followed by all of the zeros, followed by all of the positive numbers.

Example:

Input:  5, 3, 0, -6, 2, 0, 5
Output: -6, 0, 0, 3, 2, 5, 5

Note that the numbers do not need to be fully sorted: just sorted by sign.

So, the final array will look like this: -, -, ..., -, -, 0, 0, ..., 0, 0, +, +, ..., +, +

Rules

• You may only use the input array and a constant amount of additional memory (i.e. you may not create any more arrays)
• You may only use one loop, which may execute only as many times as the length of the array. You may not use built-in functions which conceal any kind of loop. This includes built-in sort functions.
• The result should be in the format I described

The winner will be the person who will submit the shortest code (counted in bytes) that changes the initial array into a correct format (like described above).

Answer 1

C, 92

This could probably be reduced by at least 10 bytes; there are many expressions going to waste.

The first argument should point to the beginning of the array; the second should point after the end of the array.

*x;f(b,e)int*b,*e;{for(x=b;x<e;x++)*x>0&&--e-x?*x--^=*e^=*x^=*e:*x<0?b-x?*x^=*b=*x:0,b++:0;}

Ungolfed with random test generator:

*x;
f(b,e)int*b,*e;{
    for(x=b;x<e;x++) {
        if(*x<0) {
            if(b == x)
                b++;
            else
                *b++ = *x, *x=0;
        } else if(*x>0 && x != --e) {
            *x^=*e^=*x^=*e;
            x--;
        }
    }
}

int main()
{
    int a[999];
    srand(time(0));
    int n = rand() % 50;
    int i;
    for(i = 0; i < n; i++) printf("%d ", a[i] = rand() % 9 - 4);
    f(a, a+n);
    puts("");
    for(i = 0; i < n; i++) printf("%d ", a[i]);
    return 0;
}

Answer 2

STATA 242

Follows the wikipedia page exactly. Thanks @PeterTaylor

Takes input as a space separated set of numbers from std in and outputs as such as well to std out.

di _r(a)
token $a//converts to array (kind of)
loc i=0
loc j=0
loc q=wordcount($a)
loc n=`q'-1
while `j'<=`n' {
loc t=``j''
if `t'<0{
loc `j'=``i''
loc `i'=`t'
loc ++i
loc ++j
}
else if `t'>0{
loc `j'=``n''
loc `n'=`t'
loc --n
}
else
loc ++j
}
//used only to output
forv x=1/`q'{
di ``x'' _c
}

Answer 3

Python 2: 116 bytes

a=input();i=j=0;n=len(a)
while j<n:b=a[j];r,s=b<0,b>0;c=i*r+n*s-s+j*(b==0);a[c],a[j]=b,a[c];i+=r;n-=s;j+=b<1
print a

This is a golfed Python translation of the Dutch national flag pseudo-code.

Possible 112 bytes

Not sure, if this is allowed. It creates a second array of size 3 (constant amount of additional memory!).

a=input();i=j=0;n=len(a)-1
while j<=n:b=a[j];k=(i,j,n)[cmp(b,0)+1];a[k],a[j]=b,a[k];i+=b<0;n-=b>0;j+=b<1
print a

Answer 4

C,90

Straightforward implementation of the algorithm in the wikipedia article per Peter Taylor's comment on the question.

Expects to find the data in an array called a like the other C answer. n,p and z are pointers for the insertion of negative and positive numbers and zeroes. n and p are taken as arguments pointing to the first and last elements of the data.

f(n,p){int t,z;for(z=n;p-z;z++)(t=a[z])?a[z]>0?a[z]=a[p],a[p--]=t:(a[z]=a[n],a[n++]=t):0;}

Answer 5

ECMAScript 157 Bytes

Takes the numbers as space separated or comma separated set from a prompt dialog and returns the result with a alert dialog.

for(v=prompt().split(/,?\s+/),s=function(j,n){t=v[j],v[j]=v[n],v[n]=t},i=j=0,n=v.length-1;j<=n;)
!(~~v[j]<0&&!s(i++,j++)||~~v[j]>0&&!s(j,n--))&&j++;alert(v);

Answer 6

PHP (146)

function f($s){for($i=0,$n=count($s)-1;$j++<=$n;)if($k=$s[$j]){$l=$k>0?n:i;$x=$s[$$l];$s[$$l]=$k;$s[$j]=$x;$k>0?$n--|$j--:$i++;}echo print_r($s);}

http://3v4l.org/ivRX5

PHP's relatively verbose variable syntax is a bit painful here...

Answer 7

Rebol - 149 142 140

a: to-block input i: j: 1 n: length? a while[j <= n][case[a/:j < 0[swap at a ++ i at a ++ j]a/:j > 0[swap at a j at a -- n]on[++ j]]]print a

This is a direct port of the Dutch national flag wikipedia pseudocode. Below is how it looks ungolfed:

a: to-block input
i: j: 1
n: length? a

while [j <= n] [
    case [
        a/:j < 0 [swap at a ++ i at a ++ j]
        a/:j > 0 [swap at a j at a -- n]
        on       [++ j]
    ]
]

print a

Usage example:

rebol dutch-flag.reb <<< "5 3 0 -6 2 0 5"
-6 0 0 2 3 5 5

NB. Rebol arrays (blocks) don't use commas - [5 3 0 -6 2 0 5]

And if its OK wrap this up into a function which takes an array and modifies it in place then we can get it down to 128 chars:

>> f: func[a][i: j: 1 n: length? a while[j <= n][case[a/:j < 0[swap at a ++ i at a ++ j]a/:j > 0[swap at a j at a -- n]on[++ j]]]n]

>> array: [5 3 0 -6 2 0 5]
== [5 3 0 -6 2 0 5]

>> print f array
-6 0 0 2 3 5 5

>> ;; and just to show that it as modified array

>> array
== [-6 0 0 2 3 5 5]

In fact if didn't need to return array (ie. just modify) then you could shave off 1 more char.

Answer 8

C++

Un-golfed solution: n counts the negatives added to front of array. For each element if negative swap with element at n, if zero swap with element at n+1 else swap with last element.

void p(int* k,int n)
{
for(int i=0;i<n;i++)
{
cout<<*(k+i)<<' ';
}
cout<<endl;
}

void s(int *x,int i,int j)
{
int t=*(x+j);
*(x+j)=*(x+i);
*(x+i)=t;
}
void f(int *x,int L)
{
int n=0;
int k;
for(int i=1;i<L;i++)
{
k=*(x+i);
if(k<0)
{
s(x,i,n);
n++;
}
else if(k==0)
{
s(x,i,n+1);
}
else if(k>0)
{
s(x,i,L-1);
}
}
}

int main()
{
int x[]={5,2,-1,0,-2,4,0,3};
f(x,8);
p(x,8);
return 0;
}

Answer 9

CJam - 72 67

q~_,(:N;{_U=:B0>{U1$N=tNBtN(:N;}{B{U1$T=tTBtT):T;}{}?U):U;}?UN>!}gp

Input: [5 3 4 0 -6 2 0 5]
Output: [-6 0 0 4 2 3 5 5]

Try it at http://cjam.aditsu.net/

Explanation:

This is another implementation of the algorithm from wikipedia, using T for i and U for j (both automatically initialized to 0).

q~                    read and evaluate the array (let's call it "A")
_,(:N;                keep A on the stack and set N ← size of A - 1  
{                     do...  
    _U=:B             keep A on the stack and set B ← A[U] (also leaving B on the stack)  
    0>{               if B > 0
        U1$N=t        A[U] ← A[N]
        NBt           A[N] ← B
        N(:N;         N ← N - 1
    }{                else
        B{            if B ≠ 0
            U1$T=t    A[U] ← A[T]
            TBt       A[T] ← B
            T):T;     T ← T + 1
        }{            else (do nothing)
        }?            end if
        U):U;         U ← U + 1
    }?                end if
UN>!}g                ...while not (U > N)
p                     print representation of A