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
code-challenge
sorting
brainfuck
Ronald
fonte
fonte
Respostas:
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 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|A2
após a troca de um. O particionamento é realizado mantendo o barramento entre os elementos alto e baixo.Aqui está a versão completa:
fonte
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.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.)
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.
fonte