From madler@tybalt.caltech.edu Fri Apr  6 22:39:21 1990
From: madler@tybalt.caltech.edu (Mark Adler)
Newsgroups: comp.sys.handhelds
Subject: A quicker quicksort for the HP-48SX
Date: 5 Apr 90 19:30:12 GMT
Distribution: comp.sys.handhelds
Organization: California Institute of Technology, Pasadena

With Alonzo's helpful comments about what operations are fast on the
HP-48SX, and why, I wrote a quicksort program faster than Alonzo's.
The speed increase comes from a different strategy (not putting the
sublists on the bottom of the stack), tighter inner loops (index
bounds do not have to be checked), a median approach to selecting the
middle element, and a final insertion sort pass to sort short
subfiles.

I tested three sorts: QSORT, ASORT, and SORT where QSORT is Alonzo's
original, ASORT is QSORT modified to stop at sublists of length 24 or
less and then do an insertion sort, and SORT is my version.  (SORT
stops at sublists of length 20---the values 20 and 24 minimize the
execution times of the respective sorts.)  They were all tested on
lists of 500 reals and 50 reals (generated using RAND) with about 18K
free before the list was made, and with lastargs turned off (flag -55
set).  The list was stored in a global and then recalled to the
stack, as per Alonzo's suggestion.  The test for 50 elements were
done for 10 different random lists each and the number that follows
is the standard deviation for the tests.  The times are in min:sec or
just seconds:

sort       500     50

QSORT     3:55  10.37 (0.71)
ASORT     3:35   7.85 (0.68)
SORT      2:45   7.13 (0.31)

SORT can be modified to use a different comparison operator than ">"
by changing the occurences of "IF DUP2 >" to "IF DUP2 GT", "PICK >"
to "PICK GT", and "PICK <" to "PICK SWAP GT" in QPART, and "PICK >"
to "PICK GT" in SORT, where GT is a program or expression that
returns zero if stack entry 2 is less than or equal to stack entry
one, or non-zero otherwise.

Mark Adler
madler@tybalt.caltech.edu

Here are the programs:

%%HP: T(3)A(R)F(.);
@ SORT crc #DBF1h length 112.5
@ Use QPART to do a quicksort up to subfiles of length 20, and then do
@ one pass of an insertion sort to sort the subfiles.
\<< OBJ\-> \-> n                        @ put list on stack
  \<< n 2 QPART                         @ do quicksort
      2 n FOR j                         @ do insertion sort
        j ROLL j 2 +                    @ get element j
        WHILE                           @ assuming [1]..[j-1] is sorted,
          DUP2 PICK >                   @  find where element j goes
        REPEAT
          1 -
        END
        2 - ROLLD                       @ put element j there
      NEXT
      n \->LIST                         @ convert back to list
  \>>
\>>

%%HP: T(3)A(R)F(.);
@ QPART crc #16E0h length 389
@ Given a partition of the stack, split it into two partitions so that
@ all the entries in the first one are less than or equal to the entries
@ in the second one, and then call this routine recusively for each of
@ those partitions.  If a partition is 20 or fewer elements, then do
@ nothing and end the recursion.  A final pass of an insertion sort will
@ sort the remaining short partitions more efficiently.
\<<
  IF DUP2 - 18 > THEN                   @ sort if more than 20 elements
    @ sort the portion of the stack from level l to level r (after
    @  l and r are pulled off the stack).
    \-> r l \<<                         @ (l is really l+1)
      @ sort [l], [m], [r] so that [l] >= [m] >= [r] where they are
      @  picked from the start, middle, and end of the sublist.
      r l + 2 / FLOOR ROLL              @ (FLOOR needed since l is l+1)
      l ROLL
      IF DUP2 > THEN SWAP END
      l ROLLD r ROLL
      IF DUP2 > THEN
        r
      ELSE
        SWAP r ROLLD l ROLL
        IF DUP2 > THEN SWAP END
        l
      END
      ROLLD
      @ start sorting inside [l], [r].
      r 3 + SWAP l 3 +
      @ put [m] in list so that [i] >= [m] >= [j] for i < j.
      WHILE                             @ stack is i+4,[m],j+4,list...
        WHILE 1 + DUP2 PICK < REPEAT END        @ now [m] >= [i]
        SWAP ROT
        WHILE 1 - DUP2 PICK > REPEAT END        @ now [j] >= [m]
        ROT DUP2 >                      @ until j <= i
      REPEAT                            @ stack is i+4,j+4,[m],list...
        DUP2 ROLL OVER ROLL             @ swap [i], [j]
        4 PICK 1 + ROLLD OVER ROLLD
        4 ROLLD SWAP DROP               @ stack is i+4,[m],j+4,list...
      END
      DROP 2 - SWAP OVER ROLLD          @ put [m] after [j]
      @ sort the sublists [j+2..r] and [l..j] by calling this program
      @  recursively.
      r SWAP DUP 'r' STO 1 + QPART
      r 2 - l QPART
    \>>
  ELSE
    DROP2                               @ not sorting---trash r and l
  END
\>>