Implementar o QuickSort no BrainF *** [fechado]

32

Conforme discutido na sala Lounge no Stack Overflow:

se você não puder implementar o algoritmo Quicksort fornecido em en.wikipedia.org/wiki/Quicksort em qualquer idioma com o mínimo de conhecimento, convém considerar uma profissão diferente. @sbi

mas a SBI também observou que talvez o BrainF *** fosse uma exceção.

Então, aqui está o quebra-cabeça / desafio: implemente o QuickSort no BrainF *** . A implementação deve

  • ser interpretado por isso e / ou pelo (s) intérprete (s) aqui (para scripts grandes)
  • implementar o algoritmo conforme descrito na Wikipedia - se possível como uma classificação no local
  • classifique a seguinte lista de números inteiros: [0,4,6,4,2,3,9,2,3,6,5,3] e imprima o resultado
Ronald
fonte
Pesquisando um pouco, sou capaz de encontrar uma implementação , mas é de 6kB (e compilada pela Haskell).
Peter Taylor
@ Peter, na verdade, a implementação do brainfuck é de 474,2 K dentro do arquivo - que é um pouco maior do que eu esperava (e grande demais para o intérprete on-line). Talvez eu deva mudar o intérprete alvo .. (mas eu amo ver algo escrito à mão)
Ronald
22
Eu aposto que eu poderia fazer bubble sort em vez disso e ninguém olhando para o código saberia a diferença ...
Peter Olson
11
@Keith a ideia é realmente implementar QuickSort, não apenas qualquer tipo que vai trabalhar ... :-)
Ronald
11
@ Peter Of The Corn: Descobriríamos uma espécie de bolha pelo mau desempenho.
usuário desconhecido

Respostas:

55

BrainF * (697 bytes)

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

Abaixo está uma versão anotada. Para acompanhar o que deveria estar acontecendo durante o desenvolvimento, usei uma notação de comentário parecida com esta:|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)

A memória é organizada com uma pilha crescente esquerda de partições para processar à esquerda, um espaço temporário no centro e a matriz sendo classificada à direita. A indexação da matriz é manipulada movendo um "barramento de dados" que contém o índice e o espaço de trabalho através da matriz. Assim, por exemplo, um ônibus de 3 largos de |i|data|0|A0|A1|A2, se tornará |A0|i-1|data|0|A1|A2após a troca de um. O particionamento é realizado mantendo o barramento entre os elementos alto e baixo.
Aqui está a versão completa:

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
fonte
Eu estava trabalhando em uma solução semelhante, mas não consegui fazê-lo funcionar. Idéia incrível para fazer o particionamento dessa maneira. Eu estava retirando um elemento de cada vez e substituindo-o, e ele ficou bastante complicado rapidamente. Eu também estava envolvido com isso, então você me destruiu em eficiência também.
precisa saber é o seguinte
11
Tudo no BF fica complicado rapidamente :) Mesmo coisas aparentemente simples, como fazer um eficiente, if (i<j) {} else {}levaram várias tentativas para acertar. E os casos extremos são assassinos. Não sei quantas vezes pensei "apenas uma coisinha sobrando ..." e descobri um caso de teste que causou várias horas de trabalho. Acho que posso reduzi-lo em algumas dezenas de caracteres, mas não tenho certeza se quero me esforçar.
precisa saber é o seguinte
Uma palavra: uau! Sinceramente, não achei que fosse humanamente possível. Eu estou indo para executar algumas entradas através dele só para ver como ele funciona :-)
Ronald
Épico! Apenas épico!
vsz
a única coisa a dizer é "caramba!"
Math chiller
11

brainfuck (178 bytes)

Mesmo se o cérebro for pesado, ajuda a trabalhar com os grãos da linguagem. Pergunte a si mesmo "Preciso armazenar esse valor explicitamente em uma célula?" Muitas vezes você pode ganhar velocidade e concisão fazendo algo mais sutil. E quando o valor é um índice de matriz (ou um número natural arbitrário), pode não caber em uma célula. Obviamente, você pode aceitar isso como um limite do seu programa. Mas projetar seu programa para lidar com grandes valores geralmente o tornará melhor de outras maneiras.

Como sempre, minha primeira versão de trabalho tinha o dobro do tempo necessário - 392 bytes. Numerosas modificações e duas ou três grandes regravações produziram esta versão de 178 bytes, relativamente simples. (Embora divertidamente uma classificação em tempo linear tenha apenas 40 bytes.)

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

Os valores de entrada são espaçados a cada três células: para cada célula de valor (V), há uma célula (L) abel (usada para navegação) e mais uma célula para (S) espaço de crachá. O layout geral da matriz é

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

Inicialmente, todas as células L são definidas como 1, para marcar partes da matriz que ainda precisam ser classificadas. Quando terminamos de particionar um subarray, o dividimos em subarrays menores, definindo a célula L de seu pivô como 0, depois localize a célula L mais à direita que ainda é 1 e particione o subarray em seguida. Estranhamente, essa é toda a contabilidade de que precisamos para lidar adequadamente com o processamento recursivo de subarrays. Quando todas as células L foram zeradas, toda a matriz é classificada.

Para particionar um subarray, puxamos seu valor mais à direita em uma célula S para atuar como pivô e o trazemos (e a célula V vazia correspondente) para a esquerda, comparando-o com o outro valor no subarray e trocando conforme necessário. No final, o pivô é trocado novamente, usando o mesmo código de troca (que economiza 50 bytes ou mais). Durante o particionamento, duas células L extras são mantidas definidas como 0, para marcar as duas células que podem precisar ser trocadas entre si; no final do particionamento, o 0 esquerdo se fundirá com o 0 à esquerda da sub-matriz e o 0 direito terminará marcando seu pivô. Esse processo também deixa 1 extra na célula L à direita do subarray; o loop principal começa e termina nesta célula.

>+>>>>>,[>+>>,]>+[                      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
fonte
11
Impressionante. É muito mais limpo quando você trabalha com os idiomas de BF, em vez de tentar forçá-lo a agir como uma linguagem processual, como eu fiz.
AShelly
Isto é; mas a versão 4, com 392 bytes, também era idiota. Esta é a versão 39 ou mais. :)
Daniel Cristofani