Prenez un tableau d'entiers contenant des nombres négatifs, des nombres positifs et des zéros. Regroupez-le avec une seule itération et en place de sorte que tous les nombres négatifs viennent en premier, suivis de tous les zéros, puis de tous les nombres positifs.

Exemple:

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

Notez que les numéros n'ont pas besoin d'être entièrement triés: juste triés par signe.

Ainsi, le tableau final ressemblera à ceci: -, -, ..., -, -, 0, 0, ..., 0, 0, +, +, ..., +, +

Règles

• Vous ne pouvez utiliser que le tableau d'entrée et une quantité constante de mémoire supplémentaire (c'est-à-dire que vous ne pouvez plus créer de tableaux)
• Vous ne pouvez utiliser qu'une seule boucle, qui peut s'exécuter seulement autant de fois que la longueur du tableau. Vous ne pouvez pas utiliser de fonctions intégrées qui cachent tout type de boucle. Cela inclut des fonctions de tri intégrées.
• Le résultat doit être dans le format que j'ai décrit

Le gagnant sera la personne qui soumettra le code le plus court (compté en octets) qui change le tableau initial dans un format correct (comme décrit ci-dessus).

C, 92

Cela pourrait probablement être réduit d'au moins 10 octets; il y a beaucoup d'expressions qui vont se perdre.

Le premier argument doit pointer vers le début du tableau; le second doit pointer après la fin du tableau.

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

Non golfé avec générateur de test aléatoire:

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

STATA 242

Suit exactement la page wikipedia. Merci @PeterTaylor

Prend l'entrée comme un ensemble de nombres séparés par un espace de std in et les sorties en tant que telles ainsi que 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
}

Python 2: 116 octets

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

Ceci est une traduction Python du golf du pseudo-code du drapeau national néerlandais.

112 octets possibles

Je ne sais pas si cela est autorisé. Il crée un deuxième tableau de taille 3 (quantité constante de mémoire supplémentaire!).

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

C, 90

Mise en œuvre simple de l'algorithme dans l'article de wikipedia par le commentaire de Peter Taylor sur la question.

S'attend à trouver les données dans un tableau appelé acomme l'autre réponse C. n, pEt zsont des pointeurs pour l'insertion des négatifs et des nombres positifs et des zéros. net psont considérés comme des arguments pointant vers le premier et le dernier élément des données.

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

ECMAScript 157 octets

Prend les nombres séparés par des espaces ou séparés par des virgules dans une boîte de dialogue d'invite et renvoie le résultat avec une boîte de dialogue d'alerte.

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

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

La syntaxe des variables relativement verbeuse de PHP est un peu pénible ici ...

Rebol - 149 142 140 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

Il s'agit d'un port direct du pseudocode wikipedia du drapeau national néerlandais. Voici à quoi il semble non golfé:

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

Exemple d'utilisation:

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

NB. Les tableaux Rebol (blocs) n'utilisent pas de virgules -[5 3 0 -6 2 0 5]

Et si son OK envelopper cela dans une fonction qui prend un tableau et le modifie en place, nous pouvons le réduire à 128 caractères:

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

En fait, si vous n'avez pas besoin de retourner un tableau (c'est-à-dire de simplement le modifier), vous pouvez raser 1 caractère de plus.

C ++

Solution sans golf: n compte les négatifs ajoutés à l'avant du tableau. Pour chaque élément si échange négatif avec élément en n, si échange nul avec élément en n + 1, sinon échange avec le dernier élément.

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

CJam - 72 67

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

Entrée: [5 3 4 0 -6 2 0 5]
Sortie:[-6 0 0 4 2 3 5 5]

Essayez-le sur http://cjam.aditsu.net/

Explication:

Il s'agit d'une autre implémentation de l'algorithme de wikipedia, utilisant Tpour iet Upour j(tous deux automatiquement initialisés à 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