Date: 15 Apr 90 17:51:39 GMT
Organization: California Institute of Technology, Pasadena
Subject: Searching on the HP-48SX
One of the main reasons one sorts is to facilitate searching. Hence
I am posting here some search routines for ordered lists to go with
the sorting routines I previously posted.
OPOS takes an ordered list and an element and returns where in that
list the element should go (possibly after the the end of the list),
and whether the element is in the list or not.
OPUT takes a list and an element and inserts the element in the proper
location in the list.
SRCH is the combination binary/linear search routine used by OPOS and
OPUT.
These routines use ">" to determine the ordering, but this operation
can be replaced to compare elements other than reals or strings. One
should view the elements of a list as records, of which some part of
the record represents a key. It is the keys of two records that the
replacement greater-than operation would compare. For example, each
record might itself be a list, the first entry of which is a string.
Then ">" would be replaced by: "1 GET SWAP 1 GET <".
Enjoy.
Mark Adler
madler@tybalt.caltech.edu
%%HP: T(3)A(R)F(.);
@ OPOS crc #C136h length 127
@
@ by Mark Adler 14 Apr 1990
@
@ Ordered POS: the arguments are a list in level 2 and the element to
@ locate in level 1. The result is the location in level 2 and a
@ boolean in level 1 which is true if the element is in the list. The
@ location has the range 1..n+1, where n is the number of entries in
@ the list. n+1 indicates the element belongs at the end of the list
@ (the boolean is always false in this case). It is assumed that the
@ input list is ordered so that the first entry is less than or equal
@ to the second entry, the second is less than or equal to the third,
@ etc.
@
@ OPOS uses SRCH to find where in the list the element goes. SRCH
@ uses the ">" operation to compare elements, but this can be changed
@ in SRCH---see the comments in SRCH. The ">" in this routine would
@ also have to be changed in the same way.
@
\<<
SWAP OBJ\-> \-> n
\<<
n 1 + ROLL n SRCH @ do search
3 - \-> k j @ save k, index
\<<
j PICK k > NOT @ see if k in list
n 1 + ROLLD n DROPN @ trash list
n j - 1 + @ compute location
SWAP @ return index, boolean
\>>
\>>
\>>
%%HP: T(3)A(R)F(.);
@ OPUT crc #5937h length 70.5
@
@ by Mark Adler 14 Apr 1990
@
@ Ordered PUT: put an element in its proper location in an ordered
@ list. The arguments are the list in level 2 and the element to
@ insert in level 1. The result is a list in level 1 that is one
@ longer than the original list. It is assumed that the input list
@ is ordered so that the first entry is less than or equal to the
@ second entry, the second is less than or equal to the third, etc.
@ This order is maintained in the resulting list.
@
@ OPUT uses SRCH to find where in the list the element goes. SRCH
@ uses the ">" operation to compare elements, but this can be changed
@ in SRCH---see the comments in SRCH.
@
\<<
SWAP OBJ\-> \-> n
\<<
n 1 + ROLL n SRCH @ do search
2 - ROLLD @ put k at right place in stack
n 1 + \->LIST @ make new list one bigger
\>>
\>>
%%HP: T(3)A(R)F(.);
@ SRCH crc #D00Bh length 145
@
@ by Mark Adler 14 Apr 1990
@
@ Search an ordered set of elements on the stack for the specified
@ element, and return the location in the stack where the element
@ should be. The input on the stack is (from bottom up):
@
@ n k list...
@
@ where n is the number of elements in the list, k is the element to
@ search for, and "list..." is n stack entries such that Õ1å >= Õ2å,
@ Õ2å >= Õ3å, etc., where Õjå is the jth entry in list..., counting
@ from the bottom. The output is:
@
@ i+3 k list...
@
@ where k and list... are unchanged and i is where in list... the
@ element k should go, i.e., k <= Õiå and k > Õi+1å.
@
@ A uniform binary search is done until the target is narrowed down to
@ 13 or fewer elements, at which point a linear search is performed.
@ This parameter can be changed for more time intensive compares by
@ changing the "7 \>=" to "6 >", "6 \>=", "5 >", etc. until the time
@ is optimized. m takes on integer or half integer values here, hence
@ the half-steps for the alterations.
@
@ The compare itself is changed at the two "PICK >"'s. Simply change
@ ">" to the appropriate sequence of operations, or change it to a
@ function call (e.g. "GT") to allow changing the compare operation on
@ the fly.
@
\<<
@ do uniform binary search (Knuth algorithm U with cutoff).
2 / DUP CEIL 4 + SWAP @ stack is m/2 i+4 k list...
WHILE DUP 7 \>= REPEAT @ do until m/2 < 7
FLOOR 2 / ROT ROT @ stack is i+4 k m'/2 list...
IF DUP2 PICK > THEN @ if k > Õiå then
3 PICK CEIL - @ i <- i - ceil(m'/2)
ELSE @ else
3 PICK CEIL + @ i <- i + ceil(m'/2)
END
ROT @ stack is m'/2 i+4 k list...
END
@ do linear search.
FLOOR + 1 - @ point i to end of sublist
WHILE DUP2 PICK > REPEAT @ stack is i+3 k list...
1 - @ decrement i until there
END @ now k <= Õiå
\>>
Date: 16 Apr 90 19:49:58 GMT
Organization: California Institute of Technology, Pasadena
Subject: Re: My last post on sorting (sure) for the HP-48SX
Oops on OPOS. Here is a corrected version of OPOS---the last one
didn't work for elements that belonged on the end of the list.
Also included here is an improved QPART using Alonzo's code for
swapping Õiå and Õjå more efficiently. (I see that Alonzo can't
resist small tweaks either.)
Mark Adler
madler@tybalt.caltech.edu
%%HP: T(3)A(R)F(.);
@ OPOS crc #DEh length 142
@
@ by Mark Adler 16 Apr 1990
@
@ Ordered POS: the arguments are a list in level 2 and the element to
@ locate in level 1. The result is the location in level 2 and a
@ boolean in level 1 which is true if the element is in the list. The
@ location has the range 1..n+1, where n is the number of entries in
@ the list. n+1 indicates the element belongs at the end of the list
@ (the boolean is always false in this case). It is assumed that the
@ input list is ordered so that the first entry is less than or equal
@ to the second entry, the second is less than or equal to the third,
@ etc.
@
@ OPOS uses SRCH to find where in the list the element goes. SRCH
@ uses the ">" operation to compare elements, but this can be changed
@ in SRCH---see the comments in SRCH. The ">" in this routine would
@ also have to be changed in the same way.
@
\<<
SWAP OBJ\-> \-> n
\<<
n 1 + ROLL n SRCH @ do search
3 - \-> k j @ save k, index
\<<
IF j DUP THEN @ if j not past end,
PICK k > NOT @ see if k in list
END
n 1 + ROLLD n DROPN @ trash list
n j - 1 + @ compute location
SWAP @ return index, boolean
\>>
\>>
\>>
%%HP: T(3)A(R)F(.);
@ QPART crc #156h length 412
@
@ by Mark Adler 16 Apr 1990
@
@ Given a partition of the stack, pick an entry in the partition and
@ split the partition into two partitions such that all the entries in
@ the first one are less than the entry picked, and all the entries in
@ the second one are greater than the entry picked, and the entry is
@ placed between them. Then call this routine recursively for each of
@ those partitions, unless the partition is 20 entries or less. A
@ final pass of an insertion sort should be done to sort the remaining
@ short partitions. The value of 20 was determined experimentally on
@ test cases of lists of random reals.
@
@ The entry for partitioning is picked using the median method, which
@ picks the median value of the entries at the beginning, middle, and
@ end of the list. This makes the sort fast for already sorted lists,
@ and greatly reduces the probability of the sort taking order n^2
@ time. It also reduces the total number of comparisons, speeding the
@ sort somewhat. Most importantly, an additional step of sorting the
@ first and last elements of the list (which adds one compare) allows
@ the inner loops of the algorithm to not have to check for the bounds
@ of the partition. This special-purpose three element sort does not
@ cost extra, since the outer two elements would have to have been
@ compared and swapped anyway if they were in the wrong place. Thanks
@ to Alonzo Gariepy for an improved swap of Õiå and Õjå.
@
@ The arguments to QPART are two integers specifying the stack levels
@ to partition. The arguments refer to the stack after the arguments
@ are removed from the stack. The integer in the first level minus 1
@ is the starting level, and the integer in level 2 is the ending level
@ to partition. So, for example, to partition the stack levels 1
@ through n, the calling sequence would be "n 2 QPART". Since QPART
@ does not check the partition size on entry, the calling routine
@ should do that and avoid calling QPART for sizes of 20 or less.
@
@ The algorithm can be modified to sort objects besides reals and
@ strings by replacing the ">" in the "IF DUP2 >"'s and in the "PICK >"
@ and replacing the "<" in the "PICK <" with the appropriate code for
@ the object. The routine can be generalized (at a speed penalty) by
@ replacing said ">"'s with "GT" and the said "<" with "SWAP GT" and
@ defining a function "GT" that does the job before doing the sort.
@
\<<
@ sort the partition of the stack from level l-1 to level r (after
@ l and r are pulled off of the stack).
\-> r l \<<
@
@ sort Õl-1å, Õmå, Õrå so that Õl-1å >= Õmå >= Õrå where m points
@ to the middle of the partition.
@
r l + 2 / FLOOR ROLL @ get Õmå
l ROLL @ get Õl-1å
IF DUP2 > THEN SWAP END @ sort Õmå, Õl-1å
l ROLLD r ROLL @ put back new Õl-1å; get Õrå
IF DUP2 > THEN @ if Õrå, Õmå sorted,
r @ then just put Õrå back
ELSE
SWAP r ROLLD l ROLL @ else sort Õrå, Õmå; get Õl-1å
IF DUP2 > THEN SWAP END @ and re-sort Õmå and Õl-1å
l @ put Õl-1å back
END
ROLLD
@
@ start sorting inside Õl-1å, Õrå since Õl-1å and Õrå are already
@ sorted. put Õmå in list so that Õiå >= Õmå >= Õjå for i < j.
@
r 3 + SWAP @ i = l-1 (loop begins "1 +")
l 3 + @ j = r-1 (since m pulled out)
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 SWAP ROLL SWAP ROLLD @ swap Õiå and Õjå
DUP2 ROLL OVER ROLLD
DROP ROT SWAP @ stack is i+4,Õmå,j+4,list...
END
DROP 2 - SWAP OVER ROLLD @ put Õmå after Õjå
@
@ sort the partitions Õj+2..rå and Õl-1..jå by calling this program
@ recursively, but only if the partition has length > 20. The
@ stack is j+2,list...
@
IF r DUP2 - -18 < THEN @ check top partition
SWAP DUP 'r' STO 1 + QPART r @ save j+2 in r
ELSE
DROP
END @ j+2 left on stack
IF 2 - l DUP2 - 18 > THEN @ check bottom partition
QPART
ELSE
DROP2
END @ leave the list on the stack
\>>
\>>
