Memesan array bilangan negatif, nol, dan positif dengan satu iterasi

9

Ambil array bilangan bulat yang berisi angka negatif, angka positif, dan nol. Kelompokkan dengan satu iterasi dan di tempat sedemikian rupa sehingga semua angka negatif didahulukan, diikuti oleh semua nol, diikuti oleh semua angka positif.

Contoh:

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

Perhatikan bahwa angka-angka tidak perlu disortir sepenuhnya: cukup disortir berdasarkan tanda.

Jadi, array terakhir akan terlihat seperti ini: -, -, ..., -, -, 0, 0, ..., 0, 0, +, +, ..., +, +

Aturan

  • Anda hanya dapat menggunakan array input dan jumlah memori tambahan yang konstan (mis. Anda tidak dapat membuat array lagi)
  • Anda hanya dapat menggunakan satu loop, yang dapat mengeksekusi hanya sebanyak panjang array. Anda tidak boleh menggunakan fungsi bawaan yang menyembunyikan segala bentuk loop. Ini termasuk fungsi sortir bawaan.
  • Hasilnya harus dalam format yang saya jelaskan

Pemenangnya adalah orang yang akan mengirimkan kode terpendek (dihitung dalam byte) yang mengubah array awal menjadi format yang benar (seperti dijelaskan di atas).

Ionică Bizău
sumber
6
Aka masalah bendera nasional Belanda .
Peter Taylor
@ PeterTaylor Thx, sekarang saya mengerti apa tugasnya!
randomra
Persis codegolf ini.stackexchange.com/questions/504/... selain penggunaan 1 iterasi dan 1 batas array.
Pengoptimal
Fungsi pengurutan bawaan tidak diizinkan, bukan?
KSFT
1
@KSFT Memanggil sort(...)tidak baik karena mungkin melakukan lebih dari satu iterasi.
Ionică Bizău

Jawaban:

3

C, 92

Ini mungkin dapat dikurangi setidaknya 10 byte; ada banyak ekspresi yang akan sia-sia.

Argumen pertama harus menunjuk ke awal array; yang kedua harus menunjuk setelah akhir 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;}

Tidak disatukan dengan generator uji acak:

*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
sumber
Saya mencoba ini di Blok Kode dan tidak dikompilasi, ada 3 kesalahan. Apa yang Anda kompilasi? x * tidak didefinisikan dan Anda membuat variabel sebelum {.
bacchusbeale
@ bacchusbeale Anda dapat mengompilasinya dengan gcc dalam mode default (C89). CodeBlocks bukan kompiler jadi saya tidak tahu kompiler mana yang Anda gunakan, tetapi ia bekerja dengan gcc. Alasannya mungkin tidak bekerja dengan semua kompiler adalah deklarasi K & R-style, yang tidak sesuai dengan standar ANSI.
feersum
1

STATA 242

Mengikuti halaman wikipedia dengan tepat. Terima kasih @PeterTaylor

Mengambil input sebagai set angka yang dipisahkan ruang dari std in dan output juga untuk 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
}
tanda
sumber
1

Python 2: 116 byte

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

Ini adalah terjemahan Python golf dari pseudo-code bendera nasional Belanda.

Kemungkinan 112 byte

Tidak yakin, apakah ini diizinkan. Ini menciptakan array kedua ukuran 3 (jumlah tambahan memori konstan!).

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
sumber
1

C, 90

Implementasi langsung dari algoritma dalam artikel wikipedia per komentar Peter Taylor pada pertanyaan.

Berharap untuk menemukan data dalam array yang disebut aseperti jawaban C lainnya. n, pdan zmerupakan petunjuk untuk memasukkan angka dan nol negatif dan positif. ndan pdiambil sebagai argumen yang menunjuk ke elemen pertama dan terakhir dari 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;}
Level River St
sumber
1

ECMAScript 157 Bytes

Mengambil angka-angka sebagai ruang yang dipisahkan atau dipisahkan dengan koma, diatur dari dialog prompt dan mengembalikan hasilnya dengan dialog peringatan.

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

Sintaks variabel PHP yang relatif verbose agak menyakitkan di sini ...

Stephen
sumber
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

Ini adalah port langsung dari kode pseudocode bendera nasional Belanda. Di bawah ini adalah tampilannya yang tidak diserang:

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

Contoh penggunaan:

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

NB. Array rebol (blok) tidak menggunakan koma -[5 3 0 -6 2 0 5]

Dan jika OK, bungkus ini menjadi fungsi yang mengambil array dan memodifikasinya, maka kita bisa mendapatkannya hingga 128 karakter:

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

Bahkan jika tidak perlu mengembalikan array (mis. Hanya memodifikasi) maka Anda bisa mencukur 1 char lagi.

draegtun
sumber
0

C ++

Solusi un-golfed: n menghitung negatif yang ditambahkan ke depan array. Untuk setiap elemen jika swap negatif dengan elemen di n, jika nol swap dengan elemen di n + 1, swap dengan elemen terakhir.

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
sumber
0

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]
Keluaran:[-6 0 0 4 2 3 5 5]

Cobalah di http://cjam.aditsu.net/

Penjelasan:

Ini adalah implementasi lain dari algoritma dari wikipedia, menggunakan Tuntuk idan Uuntuk j(keduanya secara otomatis diinisialisasi ke 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 berhenti karena SE adalah JAHAT
sumber