As documentation for the program bubble.i, I am including below the
original posting message, with the program itself deleted.  The
present program bubble.i is nearly identical to the one that was
posted.  The only difference is that I have now fixed the compiler
bug that made the temporary variable .4 necessary, so that variable
has been eliminated from the current version of the program.  The
old version of the compare-and-exchange routine, where this variable
was used, is included at the end of the file.

                           Louis Howell
                           November 24, 1991

-----------------------------------------------------------------------------

Subject: Bubble sort routine
Newsgroups: alt.lang.intercal
From: Louis Howell
Date: Thu, 7 Feb 91 18:56:34 PST

I am including below an Intercal bubble sort routine along with a
program to call it, which you may find amusing.  The program first
reads the number of elements to be sorted, then reads that many
numbers, then sorts those numbers and prints them out from highest
to lowest.  There must be at least two elements to be sorted.

There are several interesting things about this program.  First, it
uses a new version of the (2000) and (2010) decrement routine.  This
one is functionally identical to the one included with the Life program,
but is streamlined by eliminating the need for the temporary variable .3,
and thus should run significantly faster.

The program itself uses my best effort towards passing a routine as an
argument to another routine.  I have separated out the compare-and-exchange
routine from the rest of the bubble sort on the assumption that people
might want to sort different things in different ways.  You could also
use this bubble sort to sort 32 bit arrays, for example, or to sort arrays
in the opposite order, or to sort arrays starting at some index other
than 1.  It was therefore desirable to not only separate out the
compare-and-exchange function, but avoid telling the bubble sort routine
where this function is, or even what array it is sorting.  (This reduces
the bubble sort to nothing more than a nested pair of loops, but one
can easily envision wanting to do something similar with more complicated
routines.)

The program therefore operates as follows:  Main program initializes array,
then jumps to head of c-and-e routine, which immediately jumps to bubble
sort.  Return addresses for both the main program and the subroutine are
now available on the RESUME stack.  The bubble sort expects .1 to contain
the number of elements to be sorted, and proceeds to go through the
necessary loops.  Each time through the loop, the bubble sort returns to
the c-and-e routine with the indices of the elements to be compared
stored in .1 and .2; the c-and-e routine does its job then jumps back
into the bubble sort.  When the bubble sort finishes its loops it jumps
back to the main program using the return address which has been sitting
on the bottom of the stack all this time.  Main program prints out results.

The loops used by the bubble sort are equivalent to the Fortran
       DO 20 I = N,2,-1
          DO 10 J = N-1,1,-1
The way this is accomplished is pretty incomprehensible, as the loop
tests aren't independent---they share some code between them.  See how
fast you can figure out how they work.  Hint:  If you can't see why the
last statement is DO RESUME #4 (instead of #3), you have not yet
achieved enlightenment.

In the c-and-e routine the temporary variable .4 is not really necessary.
It is used to work around a bug in the array implementation which prevents
you from using two different subscripts on the same array in the same
statement.  Chances are this will be fixed before the array stuff is
released, in which case .4 should be eliminated by folding the pairs of
statements together in the obvious way.

On with the program---


  [Program deleted, see bubble.i for the current version.]


This is the original version of the compare-and-exchange routine:

	PLEASE NOTE COMPARE AND EXCHANGE ROUTINE
(500)	PLEASE ABSTAIN FROM (502)
	DO (3000) NEXT
	DO (501) NEXT
(501)   PLEASE FORGET #1
(502)   DO (3010) NEXT
	PLEASE REINSTATE (502)
	DO .4 <- ",1SUB.1"
        DO .3 <- '?.4$,1SUB.2'~'#0$#65535'
        DO .3 <- '?"'& "'",1SUB.1"~.3'~'"?'?.3~.3'$#32768"~"#0$#65535"'" $
                       ".3~.3"'~#1" $
	           #1'~#3
	DO (503) NEXT
	DO .3 <- ,1 SUB .1
	DO .4 <- ,1 SUB .2
	DO ,1 SUB .1 <- .4
	DO ,1 SUB .2 <- .3
	DO (501) NEXT
(504)   PLEASE RESUME .3
(503)   DO (504) NEXT
	PLEASE FORGET #1
	DO (501) NEXT

-- 
Louis Howell

  "But when we got into the street I viddied that thinking is for the gloopy
ones and that the oomny ones use like inspiration and what Bog sends."