Menerapkan QuickSort di BrainF *** [ditutup]

32

Seperti yang dibahas di ruang Lounge di Stack Overflow:

jika Anda tidak dapat mengimplementasikan algoritma Quicksort yang diberikan en.wikipedia.org/wiki/Quicksort dalam bahasa apa pun yang Anda memiliki pengetahuan minimal, Anda mungkin ingin mempertimbangkan profesi yang berbeda. @sbi

tapi SBI juga mencatat bahwa mungkin BrainF *** adalah pengecualian.

Jadi, inilah teka-teki / tantangannya: terapkan QuickSort di BrainF *** . Implementasinya harus

  • ditafsirkan oleh ini dan / atau oleh penerjemah di sini (untuk skrip besar)
  • mengimplementasikan algoritma seperti yang dijelaskan di Wikipedia - jika memungkinkan sebagai jenis di tempat
  • urutkan daftar bilangan bulat berikut: [0,4,6,4,2,3,9,2,3,6,5,3] dan cetak hasilnya
Ronald
sumber
Mencari-cari sedikit saya dapat menemukan satu implementasi , tapi ini 6kB (dan dikompilasi dari Haskell).
Peter Taylor
@ Peter sebenarnya implementasi brainfuck adalah 474.2 K di dalam arsip - yang sedikit lebih besar dari yang saya harapkan (dan terlalu besar untuk penerjemah online). Mungkin aku harus mengubah juru sasaran .. (tapi saya akan senang untuk melihat sesuatu yang ditulis tangan)
Ronald
22
Saya yakin saya bisa melakukan bubble sort dan tidak ada yang melihat kode akan tahu bedanya ...
Peter Olson
1
@Keith idenya adalah untuk benar-benar menerapkan QuickSort, bukan sembarang jenis yang akan bekerja ... :-)
Ronald
1
@ Peter Of The Corn: Kami akan menemukan semacam gelembung oleh kinerja yang buruk.
pengguna tidak diketahui

Jawaban:

55

BrainF * (697 bytes)

>>>>>>>>,[>,]<[[>>>+<<<-]>[<+>-]<+<]>[<<<<<<<<+>>>>>>>>-]<<<<<<<<[[>>+
>+>>+<<<<<-]>>[<<+>>-]<[>+>>+>>+<<<<<-]>[<+>-]>>>>[-<->]+<[>->+<<-[>>-
<<[-]]]>[<+>-]>[<<+>>-]<+<[->-<<[-]<[-]<<[-]<[[>+<-]<]>>[>]<+>>>>]>[-<
<+[-[>+<-]<-[>+<-]>>>>>>>>[<<<<<<<<+>>>>>>>>-]<<<<<<]<<[>>+<<-]>[>[>+>
>+<<<-]>[<+>-]>>>>>>[<+<+>>-]<[>+<-]<<<[>+>[<-]<[<]>>[<<+>[-]+>-]>-<<-
]>>[-]+<<<[->>+<<]>>[->-<<<<<[>+<-]<[>+<-]>>>>>>>>[<<<<<<<<+>>>>>>>>-]
<<]>[[-]<<<<<<[>>+>>>>>+<<<<<<<-]>>[<<+>>-]>>>>>[-[>>[<<<+>>>-]<[>+<-]
<-[>+<-]>]<<[[>>+<<-]<]]>]<<<<<<-]>[>>>>>>+<<<<<<-]<<[[>>>>>>>+<<<<<<<
-]>[<+>-]<+<]<[[>>>>>>>>+<<<<<<<<-]>>[<+>-]<+<<]>+>[<-<<[>+<-]<[<]>[[<
+>-]>]>>>[<<<<+>>>>-]<<[<+>-]>>]<[-<<+>>]>>>]<<<<<<]>>>>>>>>>>>[.>]

Di bawah ini adalah versi beranotasi. Untuk melacak apa yang seharusnya terjadi saat mengembangkannya, saya menggunakan notasi komentar yang terlihat seperti ini:|a|b=0|c=A0|@d|A0|A1|```|

|a| represents a named cell
|b=X| means we know the cell has value X, where X can be a constant or a variable name
|@d|  means the data pointer is in this cell
|A0|A1|```| is variable length array. (using ``` for ... because . is a command)

Memori ditata dengan tumpukan partisi yang sedang tumbuh untuk diproses di sebelah kiri, ruang gores di tengah, dan array diurutkan ke kanan. Array indexing ditangani dengan memindahkan "data bus" yang berisi indeks dan ruang kerja melalui array. Jadi misalnya bus 3-lebar |i|data|0|A0|A1|A2, akan menjadi |A0|i-1|data|0|A1|A2setelah bergeser dengan satu. Partisi dilakukan dengan menjaga bus antara elemen tinggi dan rendah.
Ini versi lengkapnya:

Get input
>>>>>>>> ,[>,]                      |A0|A1|```|An|@0|
Count items
<[ [>>>+<<<-]>[<+>-]<+ <]  |@0|n|0|0|A0|A1|```
Make 8wide data bus w/ stack on left
>[<<<<<<<<+>>>>>>>>-]  ```|K1=n|K0=0|Z=0|a|b|c|d|e|@f|g|X=0|A0|A1|```
K1 and K0 represent the first index to process (I) and one past the last (J)
Check if still partitions to process
<<<<<<<<[
  Copy K1 to a&c via Z
  [>>+>+>>+<<<<<-]>>[<<+>>-] ```|K1=J|K0=I|@Z=0|a=J|b|c=J|d|e|f|g|X=0|A0|A1|```
  Copy K0 to b&d via Z
  <[>+>>+>>+<<<<<-]>[<+>-] ```|K1|K0|@Z=0|a=J|b=I|c=J|d=I|e|f|g|X=0|A0|A1|```
  Check if J minus I LE 1 : Subtract d from c
  >>>>[-<->]                    |a=J|b=I|c=JminusI|@d=0|e|f|g|
  d= c==0; e = c==1
  +<[>- >+<<-[>>-<<[-]]]        |a=J|b=I|@c=0|d=c==0|e=c==1|f|g|
  if d or e is 1 then J minus I LE 1: partition empty
  >[<+>-]>[<<+>>-]<+<      |a=J|b=I|@c=isEmpty|d=1|e=0|f|g|
  If Partition Empty;
  [->-                      |a=J|b=I|@c=0|d=0|c=0|f|g|
    pop K0: Zero it and copy the remaining stack right one; inc new K0
    <<[-]<[-]<<[-]<[[>+<-]<]>>[>]<+    ``|K1|@Z=0|a=J|b=I|c=0|d=0|e|f|g|
  Else:
  >>>>]>[-                   Z|a=J|b=I|c=isEmpty=0|@d=0|e|f|g|X|A0|A1
    Move Bus right I plus 1 frames; leaving first element to left
    <<+[ -[>+<-]<-[>+<-]>>>>>>>>      (dec J as we move)
      [<<<<<<<<+>>>>>>>>-]<<<<<< ]      Z|Ai|a=J|@b=0|c=0|d|e|f|g|X|Aq
    first element becomes pivot Ap; store in b
    <<[>>+<<-]            Z|@0|a=J|b=Ap|c=0|d|e|f|g|X|Aq
    While there are more elements (J GT 0);
    >[                    Z|0|@a=J|b=Ap|c=0|d|e|f|g|X|Aq
      copy Ap to e via c
      >[>+>>+<<<-]>[<+>-]  Z|0|a=J|b=Ap|@c=0|d=0|e=Ap|f|g|X=0|Aq
       copy Aq to g via X
      >>>>>>[<+<+>>-]<[>+<-] |c|d=0|e=Ap|f|g=Aq|@X=0|Aq
      Test Aq LT Ap:  while e; mark f; clear it if g 
      <<<[ >+>[<-]<[<]           |@d=0|e|f=gLTe|g|
        if f: set d and e to 1; dec e and g 
        >>[<<+>[-]+>-]>-<<-]
      set g to 1; if d: set f 
      >>[-]+<<< [->>+<<]
      If Aq LT Ap move Aq across Bus
      >>[->- <<<<<[>+<-] <[>+<-] >>>>>>>>
        [<<<<<<<<+>>>>>>>>-] <<]  Z|0|Aq|a=J|b=Ap|c|d|e|@f=0|g=0|X=0|Ar
      Else Swap AQ w/ Aj: Build a 3wide shuttle holding J and Aq                
      >[[-] <<<<<<[>>+>>>>>+<<<<<<<-]>>[<<+>>-] |@c=0|d|e|f=0|g=0|X=J|Aq|Ar|```
      If J then dec J
      >>>>>[-
        & While J shuttle right
        [>>[<<<+>>>-]<[>+<-]<-[>+<-]>] |a=J|b=Ap|c|d|e|f|Ar|```|Aj|g=0|@X=0|Aq|
        Leave Aq out there and bring Aj back
        <<[ [>>+<<-] < ]              |a=J|b=Ap|c|d|e|@f=0|g|X=0|Ar|```|Aj|Aq|
      ]>]
    Either bus moved or last element swapped; reduce J in either case
    <<<<<<-]                 |Aq|@a=0|b=Ap|c|d|e|f|g|X|Ar|```|
    Insert Ap To right of bus
    >[>>>>>>+<<<<<<-]        |Aq|a=0|@b=0|c|d|e|f|g|Ap|Ar|```|
    Move the bus back to original location tracking pivot location
    <<[ [>>>>>>>+<<<<<<<-]>[<+>-]<+ <]     
    <[ [>>>>>>>>+<<<<<<<<-]>>[<+>-]<+ <<] |K1|K0|@Z=0|a=0|b=p|c|d|e|f|g|X|Ar|```
    if p is not 0:  put new partition on stack between K0 and K1:
    >+>[<-                                 |K1|K0|Z=0|@a=pEQ0|b=p|
      move K0 to Z; search for last K
      <<[>+<-] <[<]                           |@0|Kn|```|K1|0|Z=K0|a=0|b=p| 
      shift left until return to 0 at K0;
      >[ [<+>-] >]                            |Kn|```|K1|0|@0|Z=K0|a=0|b=p|
      put p one left of there making it K1; restore K0 from Z;
      >>>[<<<<+>>>>-]<<[<+>-]                 |Kn|```|K2|K1=p|K0|@Z=0|a=0|b=0|
    else increment K0 (special case when first partition empty) 
    >>]<[- <<+>>]              
  >>>]  End if !empty
<<<<<<] End If Partitions remaining   @K1=0|K0=0|Z=0|a|b|c|d|e|f|g|X=0|A0|A1|```
Print the Results
>>>>>>>>>>>[.>]
ASHelly
sumber
Saya sedang mengerjakan solusi yang sama tetapi tidak bisa membuatnya bekerja. Ide luar biasa untuk melakukan partisi dengan cara itu. Saya menarik satu elemen pada suatu waktu dan menggantinya, dan itu menjadi cukup rumit cukup cepat. Saya juga 1.5k ke dalamnya, jadi Anda menghancurkan saya pada efisiensi juga.
captncraig
1
Segala sesuatu di BF menjadi rumit cukup cepat :) Bahkan hal-hal yang tampaknya sederhana seperti cara melakukan yang efisien perlu if (i<j) {} else {}beberapa kali untuk melakukan yang benar. Dan kasus tepi adalah pembunuh. Saya tidak tahu berapa kali saya berpikir "hanya satu hal kecil ini yang tersisa ..." dan kemudian menemukan sebuah test case yang menyebabkan beberapa jam lagi bekerja. Saya pikir saya bisa menguranginya dengan beberapa lusin karakter, tetapi saya tidak yakin saya ingin mengusahakannya.
AShelly
Satu kata: wow! Jujur saya tidak berpikir itu mungkin secara manusiawi. Saya akan menjalankan beberapa input melalui itu hanya untuk melihat cara kerjanya :-)
Ronald
Epik! Epik saja!
vsz
satu-satunya hal untuk dikatakan adalah "suci f * ck!"
Math chiller
11

brainfuck (178 bytes)

Bahkan jika brainfuck rumit, itu membantu untuk bekerja dengan butir bahasa. Tanyakan kepada diri sendiri, "Apakah saya harus menyimpan nilai ini secara eksplisit di dalam sel?" Anda sering dapat memperoleh kecepatan dan kehebatan dengan melakukan sesuatu yang lebih halus. Dan ketika nilainya adalah indeks array (atau bilangan alami arbitrer), mungkin tidak muat dalam sel. Tentu saja, Anda bisa menerimanya sebagai batasan program Anda. Tetapi merancang program Anda untuk menangani nilai-nilai besar sering kali akan membuatnya lebih baik dengan cara lain.

Seperti biasa, versi kerja pertama saya dua kali lebih lama dari yang seharusnya — 392 byte. Sejumlah modifikasi dan dua atau tiga penulisan ulang utama menghasilkan versi 178 byte yang relatif anggun ini. (Meskipun mengherankan jenis waktu linear hanya 40 byte.)

>+>>>>>,[>+>>,]>+[--[+<<<-]<[[<+>-]<[<[->[<<<+>>>>+<-]<<[>>+>[->]<<[<]
<-]>]>>>+<[[-]<[>+<-]<]>[[>>>]+<<<-<[<<[<<<]>>+>[>>>]<-]<<[<<<]>[>>[>>
>]<+<<[<<<]>-]]+<<<]]+[->>>]>>]>[brainfuck.org>>>]

Nilai input ditempatkan setiap tiga sel: untuk setiap sel (V), ada sel abel (L) (digunakan untuk navigasi) dan satu sel lagi untuk ruang gores (S). Tata letak keseluruhan array adalah

0 1 0 0 0 SVLSVL ... SVL 0 0 0 0 0 0 ...

Awalnya semua sel L diatur ke 1, untuk menandai bagian dari array yang masih perlu disortir. Ketika kita selesai mempartisi subarray, kita membaginya menjadi subarrays yang lebih kecil dengan mengatur sel L pivot menjadi 0, kemudian menemukan sel L paling kanan yang masih 1 dan mempartisi subarray berikutnya. Anehnya, ini semua pembukuan yang kita butuhkan untuk menangani pemrosesan rekursif subarrays dengan benar. Ketika semua sel L telah memusatkan perhatian, seluruh array diurutkan.

Untuk mempartisi subarray, kami menarik nilai paling kanan ke dalam sel S untuk bertindak sebagai pivot, dan membawanya (dan sel V kosong yang sesuai) ke kiri, membandingkannya dengan nilai satu sama lain di subarray dan bertukar sesuai kebutuhan. Pada akhirnya pivot akan ditukar kembali, menggunakan kode swap yang sama (yang menghemat 50 byte atau lebih). Selama mempartisi, dua sel L ekstra disimpan set ke 0, untuk menandai dua sel yang mungkin perlu ditukar satu sama lain; di akhir partisi, 0 kiri akan menyatu dengan 0 di sebelah kiri subarray, dan 0 kanan akan berakhir menandai porosnya. Proses ini juga meninggalkan 1 tambahan di sel L di sebelah kanan subarray; loop utama dimulai dan berakhir di sel ini.

>+>>>>>,[>+>>,]>+[                      set up; for each subarray:
    --[+<<<-]<[                         find the subarray; if it exists:
        [<+>-]<[                        S=pivot; while pivot is in S:
            <[                          if not at end of subarray
                ->[<<<+>>>>+<-]         move pivot left (and copy it) 
                <<[>>+>[->]<<[<]<-]>    move value to S and compare with pivot
            ]>>>+<[[-]<[>+<-]<]>[       if pivot greater then set V=S; else:
                [>>>]+<<<-<[<<[<<<]>>+>[>>>]<-]     swap smaller value into V
                <<[<<<]>[>>[>>>]<+<<[<<<]>-]        swap S into its place
            ]+<<<                       end else and set S=1 for return path
        ]                               subarray done (pivot was swapped in)
    ]+[->>>]>>                          end "if subarray exists"; go to right
]>[brainfuck.org>>>]                    done sorting whole array; output it
Daniel Cristofani
sumber
1
Luar biasa. Jauh lebih bersih ketika Anda bekerja dengan idiom BF, alih-alih mencoba memaksanya untuk bertindak seperti bahasa prosedural, seperti yang saya lakukan.
AShelly
Ini; tetapi versi 4 pada 392 byte juga brainfuck idiomatik juga. Ini adalah versi 39 atau lebih. :)
Daniel Cristofani