9
\$\begingroup\$

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).

\$\endgroup\$
  • 6
    \$\begingroup\$ Aka the Dutch national flag problem. \$\endgroup\$ – Peter Taylor Jan 29 '15 at 16:55
  • \$\begingroup\$ @PeterTaylor Thx, now I understand what is the task! \$\endgroup\$ – randomra Jan 29 '15 at 17:19
  • \$\begingroup\$ Exactly this codegolf.stackexchange.com/questions/504/… other than the use 1 iteration and 1 array limit. \$\endgroup\$ – Optimizer Jan 29 '15 at 17:41
  • \$\begingroup\$ Built-in sort functions are not allowed, right? \$\endgroup\$ – KSFT Jan 29 '15 at 17:43
  • 1
    \$\begingroup\$ @KSFT Calling sort(...) is not fine since it probably does more than one iterations. \$\endgroup\$ – Ionică Bizău Jan 29 '15 at 17:58
3
\$\begingroup\$

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;
}
\$\endgroup\$
  • \$\begingroup\$ I tried this in Code Blocks and it does not compile, there are 3 errors. What you compiled with? x* is not defined and you made variables before {. \$\endgroup\$ – bacchusbeale Feb 1 '15 at 6:49
  • \$\begingroup\$ @bacchusbeale You can compile it with gcc in the default (C89) mode. CodeBlocks isn't a compiler so I can't tell which compiler you are using, but it works with gcc. The reason it may not work with all compilers is K&R-style declarations, which don't comply with the ANSI standard. \$\endgroup\$ – feersum Feb 1 '15 at 6:55
1
\$\begingroup\$

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
}
\$\endgroup\$
1
\$\begingroup\$

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
\$\endgroup\$
1
\$\begingroup\$

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;}
\$\endgroup\$
1
\$\begingroup\$

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);
\$\endgroup\$
0
\$\begingroup\$

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...

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$
0
\$\begingroup\$

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;
}
\$\endgroup\$
0
\$\begingroup\$

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
\$\endgroup\$

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.