brhfl.com

Bubble sort in dc

dc offers essentially nothing in the way of stack manipulation. Part of the power behind a lot of RPN/RPL HP calculators was that if you were being tidy with your stack, you rarely had to use registers. This is not the case with dc. Of course there’s also nothing resembling array sorting in dc, and I was curious how difficult it would be to implement a basic bubble sort.

As mentioned, we can’t directly manipulate stack elements (beyond swapping the two topmost values), but we can directly address elements of an array. This means that our bubble sort needs to dump the contents of the stack into an array, and potentially dump this array back onto the stack at the end (depending on what we need the sort for).

zsa0si[li:sli1+dsila>A]dsAx

This takes care of putting everything on the stack into array s. It does this by storing the number of items on the stack into register a (which we will need later – dc does not have a means of counting the number of items in an array). We start counter i at zero, and just go one at a time putting the top-of-stack into array s at index i until i is equal to a.

[1si0sclSxlc1=M]sM

The bubble sort itself requires three macros. This first one, M is our main macro, which we will ultimately begin executing to start the sort process. It sets a counter, i to one and a check register, c, to zero. Then it runs our next macro, S, which does one pass through the array. If S has changed anything by running macro R, the check register c will no longer be zeroed out, so we test for this and restart M until no changes have been made.

[lidd1-;sr;s<R1+dsila>S]sS

As mentioned, macro S does one pass of the array s. We fetch our counter, i, duplicate it twice, and decrement the top copy by one. While we work on our array, we’re always looking at i and i-1 essentially, which just makes the comparison a bit tidier at the end vs. i+1 and i. We load the values with these indices from s, compare them, and if they aren’t in order, we run macro R. We still have a copy of i on the stack at this point, so we increment it, duplicate it, store it, and compare with a to see if we’ve hit the end of the array.

[1scddd;sr1-;sli:sr1-:s]sR

Macro R does one instance of reversal. First it puts a one in the check register, c, so that M knows changes have been made to the array. At this point there is still a copy of i on the stack, which we duplicate three times. We load the i-indexed value from s, swap with a lower copy of i which we decrement by one before loading this i-1-indexed value from s. We load i again, and store the old i-1 value (our previous top-of-stack) at this index. This leaves our old i value atop the stack, with i one spot below it. We swap them, subtract one from i, and store the old i value at this new i-1 index in array s.

And that’s actually it. If we populate the stack and run our initial array-populating code before executing lMx, we’ll end up with our values sorted in array s. From here, we can [li1-d;srdsi0<U]dsUx to dump the array onto the stack such that top-of-stack is low, or 0si[lid;sr1+dsila>V]dsVx to dump the array onto the stack such that top-of-stack is high. If, say, we only need min (0;s) or max (la1-;s), these are simple tasks.

Additionally, if we wanted to get the median of these values, we can exploit the fact that dc just uses the floor of a non-whole index into an array. This allows us to avoid an evenness test by always taking ‘two’ values from the middle of the array and calculating their mean. If a is odd, then half of a will end in .5. Conversely, if a is even, half of a will end with no remainder. So we can subtract half of a by .5 to get the lower bound, and then subtract half of a by half of a mod one (either .5 or 0) and average the values at the resulting two indices: la2/d1~-;sr.5-;s+2/p.