Como se discutió en la sala Lounge en Stack Overflow:
Si no puede implementar el algoritmo Quicksort dado en en.wikipedia.org/wiki/Quicksort en cualquier idioma que tenga un conocimiento mínimo, es posible que desee considerar una profesión diferente. @sbi
pero SBI también señaló que tal vez BrainF *** fue una excepción.
Entonces, aquí está el rompecabezas / desafío: implementar QuickSort en BrainF *** . La implementación debe
code-challenge
sorting
brainfuck
Ronald
fuente
fuente
Respuestas:
BrainF * (697 bytes)
A continuación se muestra una versión anotada. Para realizar un seguimiento de lo que se suponía que estaba sucediendo mientras lo desarrollaba, utilicé una notación de comentario que se ve así:
|a|b=0|c=A0|@d|A0|A1|```|
La memoria se presenta con una pila de particiones que crece a la izquierda para procesar a la izquierda, un espacio para raspar en el centro y la matriz que se ordena a la derecha. La indexación de la matriz se maneja moviendo un "bus de datos" que contiene el índice y el espacio de trabajo a través de la matriz. Entonces, por ejemplo, un autobús de 3 anchos
|i|data|0|A0|A1|A2
se convertirá|A0|i-1|data|0|A1|A2
después de cambiar por uno. La partición se realiza manteniendo el bus entre los elementos alto y bajo.Aquí está la versión completa:
fuente
if (i<j) {} else {}
tomaron varios intentos para hacerlo bien. Y los casos extremos son asesinos. No sé cuántas veces pensé "solo quedaba esta cosita ..." y luego descubrí un caso de prueba que causó otras horas de trabajo para manejar. Creo que puedo reducirlo en unas pocas docenas de caracteres, pero no estoy seguro de querer esforzarme.brainfuck (178 bytes)
Incluso si el brainfuck es engorroso, ayuda a trabajar con el grano del lenguaje. Pregúntese "¿Tengo que almacenar este valor explícitamente en una celda?" A menudo puedes ganar velocidad y concisión haciendo algo más sutil. Y cuando el valor es un índice de matriz (o un número natural arbitrario), es posible que no quepa en una celda. Por supuesto, podría aceptar eso como un límite de su programa. Pero diseñar su programa para manejar valores grandes a menudo lo mejorará de otras maneras.
Como de costumbre, mi primera versión de trabajo fue el doble de lo necesario: 392 bytes. Numerosas modificaciones y dos o tres reescrituras importantes produjeron esta versión comparativamente elegante de 178 bytes. (Aunque de forma divertida, una ordenación de tiempo lineal es de solo 40 bytes).
Los valores de entrada están espaciados cada tres celdas: por cada celda de alor (V), hay una celda (L) abel (utilizada para la navegación) y una celda más para el espacio de bloqueo (S). El diseño general de la matriz es
0 1 0 0 0 SVLSVL ... SVL 0 0 0 0 0 0 ...
Inicialmente, todas las celdas L se configuran en 1, para marcar partes de la matriz que aún necesitan ser ordenadas. Cuando hayamos terminado de particionar un subconjunto, lo dividimos en subconjuntos más pequeños al establecer la celda L de su pivote en 0, luego ubicamos la celda L más a la derecha que todavía es 1 y luego dividimos esa subarregla. Curiosamente, esta es toda la contabilidad que necesitamos para manejar adecuadamente el procesamiento recursivo de las submatrices. Cuando todas las celdas L se han puesto a cero, se ordena toda la matriz.
Para dividir un subconjunto, extraemos su valor más a la derecha en una celda S para que actúe como pivote, y lo llevamos (y la correspondiente celda V vacía) a la izquierda, comparándolo con el valor del otro en el subconjunto e intercambiando según sea necesario. Al final, el pivote se intercambia nuevamente, utilizando el mismo código de intercambio (que ahorra 50 bytes más o menos). Durante la partición, dos celdas L adicionales se mantienen establecidas en 0, para marcar las dos celdas que pueden necesitar intercambiarse entre sí; al final de la partición, el 0 izquierdo se fusionará con el 0 a la izquierda del subconjunto, y el 0 derecho terminará marcando su pivote. Este proceso también deja un 1 extra en la celda L a la derecha de la submatriz; El bucle principal comienza y termina en esta celda.
fuente