Ordenar una matriz de enteros negativos, cero y positivos con una iteración

9

Tome una matriz de enteros que contengan números negativos, números positivos y ceros. Agrúpelo con una iteración y en su lugar de manera que todos los números negativos sean los primeros, seguidos de todos los ceros, seguidos de todos los números positivos.

Ejemplo:

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

Tenga en cuenta que los números no necesitan estar completamente ordenados: solo ordenados por signo.

Entonces, la matriz final se verá así: -, -, ..., -, -, 0, 0, ..., 0, 0, +, +, ..., +, +

Reglas

  • Solo puede usar la matriz de entrada y una cantidad constante de memoria adicional (es decir, no puede crear más matrices)
  • Solo puede usar un bucle, que puede ejecutarse solo tantas veces como la longitud de la matriz. No puede utilizar funciones integradas que oculten ningún tipo de bucle. Esto incluye funciones de clasificación incorporadas.
  • El resultado debe estar en el formato que describí

El ganador será la persona que presentará el código más corto (contado en bytes) que cambia la matriz inicial a un formato correcto (como se describe anteriormente).

Ionică Bizău
fuente
66
También conocido como el problema de la bandera nacional holandesa .
Peter Taylor
@PeterTaylor Thx, ¡ahora entiendo cuál es la tarea!
randomra
Exactamente este codegolf.stackexchange.com/questions/504/… que no sea el uso de 1 iteración y 1 límite de matriz.
Optimizador
Las funciones de clasificación incorporadas no están permitidas, ¿verdad?
KSFT
1
@KSFT Calling sort(...)no está bien, ya que probablemente realiza más de una iteración.
Ionică Bizău

Respuestas:

3

C, 92

Esto probablemente podría reducirse en al menos 10 bytes; hay muchas expresiones que se desperdician.

El primer argumento debe apuntar al comienzo de la matriz; el segundo debe apuntar después del final de la matriz.

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

Sin golfista con generador de prueba aleatorio:

*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;
}
Feersum
fuente
Intenté esto en Code Blocks y no se compila, hay 3 errores. ¿Con qué compilaste? x * no está definido e hizo variables antes de {.
bacchusbeale 01 de
@bacchusbeale Puede compilarlo con gcc en el modo predeterminado (C89). CodeBlocks no es un compilador, así que no puedo decir qué compilador está utilizando, pero funciona con gcc. La razón por la que puede no funcionar con todos los compiladores son las declaraciones de estilo K&R, que no cumplen con el estándar ANSI.
feersum
1

STATA 242

Sigue la página de Wikipedia exactamente. Gracias @PeterTaylor

Toma la entrada como un conjunto de números separados por espacios desde la entrada estándar y las salidas como tales también para salida estándar.

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
}
comentarios
fuente
1

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

Esta es una traducción en Python del pseudocódigo de la bandera nacional holandesa.

Posibles 112 bytes

No estoy seguro, si esto está permitido. Crea una segunda matriz de tamaño 3 (¡cantidad constante de memoria adicional!).

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
Jakube
fuente
1

C, 90

Implementación directa del algoritmo en el artículo de wikipedia según el comentario de Peter Taylor sobre la pregunta.

Espera encontrar los datos en una matriz llamada acomo la otra respuesta C. n, py zson punteros para la inserción de números negativos y positivos y ceros. ny pse toman como argumentos que apuntan al primer y último elemento de los datos.

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;}
Level River St
fuente
1

ECMAScript 157 Bytes

Toma los números como un conjunto separado por espacios o por comas de un cuadro de diálogo y devuelve el resultado con un cuadro de diálogo de alerta.

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);
fxdapokalypse
fuente
0

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 sintaxis variable relativamente detallada de PHP es un poco dolorosa aquí ...

Stephen
fuente
0

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

Este es un puerto directo del pseudocódigo wikipedia de la bandera nacional holandesa. A continuación se muestra cómo se ve sin 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

Ejemplo de uso:

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

NÓTESE BIEN. Las matrices Rebol (bloques) no usan comas -[5 3 0 -6 2 0 5]

Y si está bien, envuelva esto en una función que tome una matriz y la modifique en su lugar, entonces podemos reducirlo a 128 caracteres:

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

De hecho, si no fuera necesario devolver la matriz (es decir, simplemente modificar), podría eliminar 1 carácter más.

draegtun
fuente
0

C ++

Solución sin golf: n cuenta los negativos agregados al frente de la matriz. Para cada elemento si el intercambio negativo con el elemento en n, si el intercambio cero con el elemento en n + 1 más intercambie con el último elemento.

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;
}
bacchusbeale
fuente
0

CJam - 72 67

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

Entrada: [5 3 4 0 -6 2 0 5]
Salida:[-6 0 0 4 2 3 5 5]

Pruébalo en http://cjam.aditsu.net/

Explicación:

Esta es otra implementación del algoritmo de wikipedia, usando Tfor iy Ufor j(ambos inicializados automáticamente a 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
aditsu renunció porque SE es MALO
fuente