The most obvious methods of sorting in this case are min/maxsort and bubblesort. Frankly, while we can imagine implementing e.g. mergesort, we really don't recommend it :) Moreover, the time complexity of any sophisticated sorted algorithm would exceed O(N2) in Quack and therefore such algorithm is not suitable. In this solution we will implement minsort. It is also possible to implement acceptable version of bubblesort.
The idea is simple. In each pass we select the smallest not-yet-sorted number, print it and throw it away. When we run out of numbers, we are done and may quit.
The only problem is actually selecting the smallest number. We would like to do something like: Register a holds the smallest number so far. Get a number into b. Compare them. If the number in b is smaller, put the contents of a back into the queue and move the contents of b into a. The only thing that is not straightforward is the last step.
If we cannot move the contents, let's not move it! Instead we will remember whether the current smallest number is stored in a or in b. Yeah, right, remember... But how? Another register holding 0 or 1? Uh, but how do you suppose we change its value? Well, we will remember the information using the program counter (i.e. our position in the program)!
The actual code follows and is explained below.
:start 0 >a Zaend :smalla >b Zbprinta Gabdropa :dropb <b Jsmalla :smallb >a Zaprintb Gbadropb :dropa <a Jsmallb :printa Pa Jstart :printb Pb Jstart :end
The program runs in a loop (:start, Jstart). Each pass through this loop corresponds to one pass through the numbers in the queue. The pass starts by pushing a zero as an end marker. The first number is loaded into a. If it is already zero, we are done. Otherwise we are in the situation that a contains the smallest number so far. This situation corresponds to lines 5-11 (:smalla to Jsmalla). Next number is loaded into b. If it is greater, we drop it and continue. Otherwise we drop the value in a and jump to the other part of the program – corresponding to the situation that the minimum is in b. If at any time we get the zero, the contents of the "current" register is printed and a new pass starts.
This program needs exactly 220380 steps to sort any sequence of 250 numbers. This number of steps probably cannot be reduced by a substantial margin.
We will use the most straightforward method to write a quine (i.e. a program that prints its source). A program usually consists of two parts: data and code.
In our case data will obviously be a sequence of numbers. Imagine a program, whose code part simply takes the data, interprets it as ASCII values of characters and prints these characters. Writing this code is trivial.
Second step: how to select the data? We want to print the source of the program. The only part we have so far is our first code. What happens when we take the ASCII values of code as data? We obtain a program that prints its own code part. We are not done yet, but we already made a major step.
What remains is to print the data part. Nothing could be simpler. We will slightly modify our code. The new code2 will do the following:
In the first step this program will correctly print its data part. If we choose data to be ASCII values of code2, in the second step the program will correctly print its code part.
A slightly commented code2 follows.
We assume data is a zero-terminated sequence of numbers. In the first pass we print the data as numbers.
:1 >a Za2 Pa <a J1
Zero is pushed at the end of the sequence again. Each of the numbers is printed as a character until we encounter the zero.
:2 0 :3 >a Za4 Ca J3 :4