Zaimplementuj QuickSort w BrainF *** [zamknięte]

Jak omówiono w salonie w przepełnieniu stosu:

jeśli nie możesz wdrożyć algorytmu Quicksort podanego en.wikipedia.org/wiki/Quicksort w dowolnym języku, który znasz minimalnie, możesz rozważyć inny zawód. @sbi

ale SBI zauważyło również, że może BrainF *** był wyjątkiem.

Oto zagadka / wyzwanie: zaimplementuj QuickSort w BrainF *** . Wdrożenie musi

• być interpretowanym przez to i / lub tłumacza tutaj (dla dużych skryptów)
• wdrożyć algorytm opisany na Wikipedii - jeśli to możliwe, jako sortowanie lokalne
• posortuj następującą listę liczb całkowitych: [0,4,6,4,2,3,3,2,3,6,6,5,3] i wydrukuj wynik

BrainF * (697 bajtów)

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

Poniżej znajduje się wersja z adnotacjami. Aby śledzić, co miało się wydarzyć podczas jego opracowywania, użyłem notacji komentarza, która wygląda następująco:|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)

Pamięć jest ułożona z rosnącym w lewo stosem partycji do przetwarzania po lewej stronie, miejscem na zarysowania pośrodku i tablicą sortowaną po prawej stronie. Indeksowanie tablic odbywa się poprzez przeniesienie „szyny danych” zawierającej indeks i przestrzeń roboczą przez tablicę. Na przykład 3-szerokościowy autobus |i|data|0|A0|A1|A2stanie się |A0|i-1|data|0|A1|A2po zmianie o jeden. Partycjonowanie odbywa się poprzez utrzymanie magistrali między elementami wysokimi i niskimi.
Oto pełna wersja:

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

brainfuck (178 bajtów)

Nawet jeśli pieprzenie mózgu jest uciążliwe, pomaga pracować z ziarnem języka. Zadaj sobie pytanie „Czy muszę wyraźnie przechowywać tę wartość w komórce?” Często można uzyskać szybkość i zwięzłość, robiąc coś bardziej subtelnego. A gdy wartość jest indeksem tablicowym (lub dowolną liczbą naturalną), może nie zmieścić się w komórce. Oczywiście możesz zaakceptować to jako ograniczenie swojego programu. Ale zaprojektowanie programu do obsługi dużych wartości często poprawi go na inne sposoby.

Jak zwykle moja pierwsza działająca wersja była dwa razy dłuższa niż potrzebna - 392 bajty. Liczne modyfikacje i dwa lub trzy duże przepisywania spowodowały, że ta stosunkowo wdzięczna 178-bajtowa wersja. (Choć zabawnie, sortowanie według czasu liniowego ma tylko 40 bajtów.)

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

Wartości wejściowe są rozmieszczone co trzy komórki: dla każdej (V) komórki alue jest komórka abel (L) (używana do nawigacji) i jeszcze jedna komórka dla (S) przestrzeni do rysowania. Ogólny układ tablicy to

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

Początkowo wszystkie komórki L są ustawione na 1, aby oznaczyć części tablicy, które nadal wymagają sortowania. Kiedy skończymy dzielenie podtablicy, dzielimy ją na mniejsze podgrupy, ustawiając komórkę L jej osi przestawnej na 0, a następnie lokalizujemy skrajnie prawą komórkę L, która wciąż jest 1, i dzielimy tę podtablicę dalej. Dziwne, to wszystko, czego potrzebujemy do prowadzenia księgowości, aby poprawnie obsłużyć rekurencyjne przetwarzanie subarrays. Po wyzerowaniu wszystkich komórek L cała tablica jest sortowana.

Aby podzielić tablicę podrzędną, przeciągamy jej skrajną prawą wartość do komórki S, aby działała jako oś obrotu, i pozostawiamy ją (i odpowiadającą jej pustą komórkę V) w lewo, porównując ją ze sobą w podtablicy i zamieniając w razie potrzeby. Na końcu oś przestawiana jest z powrotem, przy użyciu tego samego kodu wymiany (co oszczędza około 50 bajtów). Podczas dzielenia dwie dodatkowe komórki L są ustawione na 0, aby zaznaczyć dwie komórki, które mogą wymagać wymiany; pod koniec podziału lewe 0 połączy się z 0 po lewej stronie podtablicy, a prawe 0 zakończy się zaznaczeniem jego osi obrotu. Ten proces pozostawia dodatkowo 1 w komórce L na prawo od podtablicy; główna pętla zaczyna się i kończy w tej komórce.

>+>>>>>,[>+>>,]>+[                      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