Implementiere QuickSort in BrainF *** [closed]

32

Wie im Lounge-Raum zum Stapelüberlauf beschrieben:

Wenn Sie den Quicksort-Algorithmus von en.wikipedia.org/wiki/Quicksort nicht in einer Sprache implementieren können, in der Sie nur minimale Kenntnisse haben, sollten Sie einen anderen Beruf in Betracht ziehen. @sbi

aber SBI merkte auch an, dass vielleicht BrainF *** eine Ausnahme war.

Also, hier ist das Rätsel / die Herausforderung: Implementiere QuickSort in BrainF *** . Die Umsetzung muss

  • von diesem und / oder dem / den Dolmetscher (n) hier interpretiert werden (für große Skripte)
  • Implementieren Sie den Algorithmus wie in Wikipedia beschrieben - wenn möglich als In-Place-Sortierung
  • sortiere die folgende Liste von ganzen Zahlen: [0,4,6,4,2,3,9,3,6,5,3] und drucke das Ergebnis aus
Ronald
quelle
Wenn ich mich ein bisschen umsehe, kann ich eine Implementierung finden , aber sie ist 6 KB groß (und von Haskell kompiliert).
Peter Taylor
@Peter tatsächlich ist die Brainfuck-Implementierung im Archiv 474,2 K groß - etwas größer als ich erwartet hatte (und zu groß für den Online-Interpreter). Vielleicht sollte ich den
Ronald
22
Ich wette, ich könnte stattdessen eine Blasensortierung durchführen, und niemand, der sich den Code ansieht, würde den Unterschied erkennen ...
Peter Olson,
1
@ Keith die Idee ist, QuickSort wirklich zu implementieren, nicht irgendeine Art, die funktionieren wird ... :-)
Ronald
1
@Peter Of The Corn: Wir würden durch die schlechte Leistung eine Blasensorte entdecken.
Benutzer unbekannt

Antworten:

55

BrainF * (697 Bytes)

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

Unten ist eine kommentierte Version. Um zu verfolgen, was während der Entwicklung passieren sollte, habe ich eine Kommentarnotation verwendet, die so aussieht:|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)

Der Speicher ist mit einem links wachsenden Stapel zu verarbeitender Partitionen, einem Arbeitsbereich in der Mitte und einem rechts sortierten Array ausgestattet. Die Array-Indizierung wird durchgeführt, indem ein "Datenbus", der den Index und den Arbeitsbereich enthält, durch das Array bewegt wird. So wird zum Beispiel ein 3er-Bus von |i|data|0|A0|A1|A2, |A0|i-1|data|0|A1|A2nach dem um eins verschoben wird. Die Unterteilung wird durchgeführt, indem der Bus zwischen dem hohen und dem niedrigen Element gehalten wird.
Hier ist die Vollversion:

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
>>>>>>>>>>>[.>]
Ahelly
quelle
Ich arbeitete an einer ähnlichen Lösung, konnte sie aber nicht ganz zum Laufen bringen. Tolle Idee, die Partitionierung so durchzuführen. Ich habe jeweils ein Element herausgezogen und ersetzt, und es wurde ziemlich schnell umständlich. Ich war auch 1,5 km dabei, also hast du mich auch aus Effizienzgründen zerstört.
captncraig
1
Alles in BF wird ziemlich schnell umständlich :) Selbst scheinbar einfache Dinge wie das effiziente Arbeiten erforderten if (i<j) {} else {}mehrere Versuche, um es richtig zu machen. Und die Randfälle sind Mörder. Ich weiß nicht, wie oft ich dachte "nur dieses eine kleine Ding ist noch übrig ..." und dann einen Testfall entdeckte, der weitere Stunden Arbeit verursachte. Ich glaube, ich kann es um ein paar Dutzend Zeichen reduzieren, bin mir aber nicht sicher, ob ich mich anstrengen möchte.
AShelly
Ein Wort: Wow! Ich habe ehrlich gesagt nicht gedacht, dass es menschlich möglich ist. Ich werde ein paar Eingaben durchgehen, um zu sehen, wie es funktioniert :-)
Ronald
Epos! Einfach episch!
vsz
das einzige was zu sagen ist "Holy F * Ck!"
Math Chiller
11

Brainfuck (178 Bytes)

Auch wenn Brainfuck umständlich ist, hilft es, mit der Körnung der Sprache zu arbeiten. Fragen Sie sich: "Muss ich diesen Wert explizit in einer Zelle speichern?" Sie können häufig an Geschwindigkeit und Präzision gewinnen, indem Sie etwas Feinsinnigeres tun. Und wenn der Wert ein Arrayindex (oder eine beliebige natürliche Zahl) ist, passt er möglicherweise nicht in eine Zelle. Natürlich können Sie dies als Grenze Ihres Programms akzeptieren. Das Entwerfen Ihres Programms für den Umgang mit großen Werten verbessert es jedoch häufig auf andere Weise.

Wie üblich war meine erste Arbeitsversion doppelt so lang wie nötig - 392 Bytes. Zahlreiche Modifikationen und zwei oder drei größere Änderungen führten zu dieser vergleichsweise eleganten 178-Byte-Version. (Obwohl eine lineare Zeitsortierung amüsanterweise nur 40 Bytes umfasst.)

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

Die Eingabewerte sind in Abständen von jeweils drei Zellen angeordnet: Für jede (V) Wertezelle gibt es eine (L) Wertezelle (für die Navigation) und eine weitere Zelle für den (S) Cratch-Raum. Das Gesamtlayout des Arrays ist

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

Zu Beginn werden alle L-Zellen auf 1 gesetzt, um Teile des Arrays zu markieren, die noch sortiert werden müssen. Wenn wir mit dem Partitionieren eines Subarrays fertig sind, teilen wir es in kleinere Subarrays auf, indem wir die L-Zelle des Pivots auf 0 setzen, dann die am weitesten rechts liegende L-Zelle ausfindig machen, die noch 1 ist, und das Subarray als nächstes partitionieren. Seltsamerweise ist dies die gesamte Buchhaltung, die wir benötigen, um die rekursive Verarbeitung von Subarrays ordnungsgemäß zu handhaben. Wenn alle L-Zellen auf Null gesetzt wurden, wird das gesamte Array sortiert.

Um ein Subarray zu partitionieren, ziehen wir seinen äußersten rechten Wert in eine S-Zelle, um als Drehpunkt zu fungieren, und bringen ihn (und die entsprechende leere V-Zelle) nach links, vergleichen ihn mit dem Wert im Subarray und tauschen ihn nach Bedarf aus. Am Ende wird der Pivot mit demselben Swap-Code (der ungefähr 50 Bytes spart) wieder eingelagert. Während der Partitionierung werden zwei zusätzliche L-Zellen auf 0 gesetzt, um die zwei Zellen zu markieren, die möglicherweise gegeneinander ausgetauscht werden müssen. Am Ende der Partitionierung verschmilzt die linke 0 mit der 0 links vom Subarray und die rechte 0 markiert den Drehpunkt. Bei diesem Vorgang verbleibt außerdem eine zusätzliche 1 in der L-Zelle rechts neben dem Subarray. Die Hauptschleife beginnt und endet an dieser Zelle.

>+>>>>>,[>+>>,]>+[                      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
quelle
1
Genial. Es ist so viel sauberer, wenn Sie mit BFs Redewendungen arbeiten, anstatt sie zu zwingen, sich wie eine prozedurale Sprache zu verhalten, wie ich es getan habe.
AShelly
Es ist; aber Version 4 mit 392 Bytes war auch idiomatisch. Dies ist Version 39 oder so. :)
Daniel Cristofani