|
996
|
1
|
|
|
2 As documentation for the program bubble.i, I am including below the
|
|
|
3 original posting message, with the program itself deleted. The
|
|
|
4 present program bubble.i is nearly identical to the one that was
|
|
|
5 posted. The only difference is that I have now fixed the compiler
|
|
|
6 bug that made the temporary variable .4 necessary, so that variable
|
|
|
7 has been eliminated from the current version of the program. The
|
|
|
8 old version of the compare-and-exchange routine, where this variable
|
|
|
9 was used, is included at the end of the file.
|
|
|
10
|
|
|
11 Louis Howell
|
|
|
12 November 24, 1991
|
|
|
13
|
|
|
14 -----------------------------------------------------------------------------
|
|
|
15
|
|
|
16 Subject: Bubble sort routine
|
|
|
17 Newsgroups: alt.lang.intercal
|
|
|
18 From: Louis Howell
|
|
|
19 Date: Thu, 7 Feb 91 18:56:34 PST
|
|
|
20
|
|
|
21 I am including below an Intercal bubble sort routine along with a
|
|
|
22 program to call it, which you may find amusing. The program first
|
|
|
23 reads the number of elements to be sorted, then reads that many
|
|
|
24 numbers, then sorts those numbers and prints them out from highest
|
|
|
25 to lowest. There must be at least two elements to be sorted.
|
|
|
26
|
|
|
27 There are several interesting things about this program. First, it
|
|
|
28 uses a new version of the (2000) and (2010) decrement routine. This
|
|
|
29 one is functionally identical to the one included with the Life program,
|
|
|
30 but is streamlined by eliminating the need for the temporary variable .3,
|
|
|
31 and thus should run significantly faster.
|
|
|
32
|
|
|
33 The program itself uses my best effort towards passing a routine as an
|
|
|
34 argument to another routine. I have separated out the compare-and-exchange
|
|
|
35 routine from the rest of the bubble sort on the assumption that people
|
|
|
36 might want to sort different things in different ways. You could also
|
|
|
37 use this bubble sort to sort 32 bit arrays, for example, or to sort arrays
|
|
|
38 in the opposite order, or to sort arrays starting at some index other
|
|
|
39 than 1. It was therefore desirable to not only separate out the
|
|
|
40 compare-and-exchange function, but avoid telling the bubble sort routine
|
|
|
41 where this function is, or even what array it is sorting. (This reduces
|
|
|
42 the bubble sort to nothing more than a nested pair of loops, but one
|
|
|
43 can easily envision wanting to do something similar with more complicated
|
|
|
44 routines.)
|
|
|
45
|
|
|
46 The program therefore operates as follows: Main program initializes array,
|
|
|
47 then jumps to head of c-and-e routine, which immediately jumps to bubble
|
|
|
48 sort. Return addresses for both the main program and the subroutine are
|
|
|
49 now available on the RESUME stack. The bubble sort expects .1 to contain
|
|
|
50 the number of elements to be sorted, and proceeds to go through the
|
|
|
51 necessary loops. Each time through the loop, the bubble sort returns to
|
|
|
52 the c-and-e routine with the indices of the elements to be compared
|
|
|
53 stored in .1 and .2; the c-and-e routine does its job then jumps back
|
|
|
54 into the bubble sort. When the bubble sort finishes its loops it jumps
|
|
|
55 back to the main program using the return address which has been sitting
|
|
|
56 on the bottom of the stack all this time. Main program prints out results.
|
|
|
57
|
|
|
58 The loops used by the bubble sort are equivalent to the Fortran
|
|
|
59 DO 20 I = N,2,-1
|
|
|
60 DO 10 J = N-1,1,-1
|
|
|
61 The way this is accomplished is pretty incomprehensible, as the loop
|
|
|
62 tests aren't independent---they share some code between them. See how
|
|
|
63 fast you can figure out how they work. Hint: If you can't see why the
|
|
|
64 last statement is DO RESUME #4 (instead of #3), you have not yet
|
|
|
65 achieved enlightenment.
|
|
|
66
|
|
|
67 In the c-and-e routine the temporary variable .4 is not really necessary.
|
|
|
68 It is used to work around a bug in the array implementation which prevents
|
|
|
69 you from using two different subscripts on the same array in the same
|
|
|
70 statement. Chances are this will be fixed before the array stuff is
|
|
|
71 released, in which case .4 should be eliminated by folding the pairs of
|
|
|
72 statements together in the obvious way.
|
|
|
73
|
|
|
74 On with the program---
|
|
|
75
|
|
|
76
|
|
|
77 [Program deleted, see bubble.i for the current version.]
|
|
|
78
|
|
|
79
|
|
|
80 This is the original version of the compare-and-exchange routine:
|
|
|
81
|
|
|
82 PLEASE NOTE COMPARE AND EXCHANGE ROUTINE
|
|
|
83 (500) PLEASE ABSTAIN FROM (502)
|
|
|
84 DO (3000) NEXT
|
|
|
85 DO (501) NEXT
|
|
|
86 (501) PLEASE FORGET #1
|
|
|
87 (502) DO (3010) NEXT
|
|
|
88 PLEASE REINSTATE (502)
|
|
|
89 DO .4 <- ",1SUB.1"
|
|
|
90 DO .3 <- '?.4$,1SUB.2'~'#0$#65535'
|
|
|
91 DO .3 <- '?"'& "'",1SUB.1"~.3'~'"?'?.3~.3'$#32768"~"#0$#65535"'" $
|
|
|
92 ".3~.3"'~#1" $
|
|
|
93 #1'~#3
|
|
|
94 DO (503) NEXT
|
|
|
95 DO .3 <- ,1 SUB .1
|
|
|
96 DO .4 <- ,1 SUB .2
|
|
|
97 DO ,1 SUB .1 <- .4
|
|
|
98 DO ,1 SUB .2 <- .3
|
|
|
99 DO (501) NEXT
|
|
|
100 (504) PLEASE RESUME .3
|
|
|
101 (503) DO (504) NEXT
|
|
|
102 PLEASE FORGET #1
|
|
|
103 DO (501) NEXT
|
|
|
104
|
|
|
105 --
|
|
|
106 Louis Howell
|
|
|
107
|
|
|
108 "But when we got into the street I viddied that thinking is for the gloopy
|
|
|
109 ones and that the oomny ones use like inspiration and what Bog sends."
|
