Implémenter QuickSort dans BrainF *** [fermé]

Comme discuté dans le salon sur Stack Overflow:

si vous ne pouvez pas implémenter l'algorithme Quicksort donné en.wikipedia.org/wiki/Quicksort dans n'importe quelle langue que vous avez une connaissance minimale, vous voudrez peut-être envisager une profession différente. @sbi

mais SBI a également noté que BrainF *** était peut-être une exception.

Voici donc le puzzle / défi: implémentez QuickSort dans BrainF *** . La mise en œuvre doit

• être interprété par ceci et / ou par les interprètes ici (pour les gros scripts)
• implémenter l'algorithme comme décrit sur Wikipedia - si possible comme un tri sur place
• trier la liste suivante d'entiers: [0,4,6,4,2,3,9,2,3,6,5,3] et imprimer le résultat

BrainF * (697 octets)

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

Voici une version annotée. Afin de garder une trace de ce qui devait se produire lors de son développement, j'ai utilisé une notation de commentaire qui ressemble à ceci:|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)

La mémoire est disposée avec une pile croissante de partitions à traiter à gauche, un espace de travail au centre et le tableau trié à droite. L'indexation des tableaux est gérée en déplaçant un "bus de données" contenant l'index et l'espace de travail à travers le tableau. Ainsi, par exemple, un bus à 3 voies de |i|data|0|A0|A1|A2, deviendra |A0|i-1|data|0|A1|A2après un décalage d'un. Le partitionnement est effectué en gardant le bus entre les éléments haut et bas.
Voici la version complète:

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 octets)

Même si le brainfuck est lourd, cela aide à travailler avec le grain de la langue. Demandez-vous "Dois-je stocker cette valeur explicitement dans une cellule?" Vous pouvez souvent gagner en vitesse et en concision en faisant quelque chose de plus subtil. Et lorsque la valeur est un index de tableau (ou un nombre naturel arbitraire), elle peut ne pas tenir dans une cellule. Bien sûr, vous pouvez simplement accepter cela comme une limite de votre programme. Mais la conception de votre programme pour gérer de grandes valeurs l'améliorera souvent par d'autres moyens.

Comme d'habitude, ma première version de travail était deux fois plus longue que nécessaire - 392 octets. De nombreuses modifications et deux ou trois réécritures majeures ont produit cette version relativement gracieuse de 178 octets. (Bien qu'amusamment, une sorte de temps linéaire n'est que de 40 octets.)

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

Les valeurs d'entrée sont espacées toutes les trois cellules: pour chaque cellule de valeur (V), il y a une cellule (L) abel (utilisée pour la navigation) et une cellule de plus pour (S) l'espace de capture. La disposition générale du tableau est

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

Initialement, toutes les cellules L sont définies sur 1, pour marquer les parties du tableau qui doivent encore être triées. Lorsque nous avons terminé de partitionner un sous-tableau, nous le divisons en sous-réseaux plus petits en définissant la cellule L de son pivot sur 0, puis localisons la cellule L la plus à droite qui est toujours 1 et partitionnons ce sous-tableau suivant. Curieusement, c'est toute la comptabilité dont nous avons besoin pour gérer correctement le traitement récursif des sous-réseaux. Lorsque toutes les cellules L ont été mises à zéro, l'ensemble du tableau est trié.

Pour partitionner un sous-tableau, nous tirons sa valeur la plus à droite dans une cellule S pour agir comme pivot, et l'amener (et la cellule V vide correspondante) à gauche, en le comparant aux autres valeurs du sous-tableau et en échangeant si nécessaire. À la fin, le pivot est de nouveau échangé, en utilisant le même code de swap (ce qui économise environ 50 octets). Pendant le partitionnement, deux cellules L supplémentaires sont maintenues à 0, pour marquer les deux cellules qui peuvent avoir besoin d'être échangées l'une avec l'autre; à la fin du partitionnement, le 0 gauche fusionnera avec le 0 à gauche du sous-tableau, et le 0 droit finira par marquer son pivot. Ce processus laisse également un 1 supplémentaire dans la cellule L à droite du sous-tableau; la boucle principale commence et se termine à cette cellule.

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