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