Article 1853 of comp.sys.handhelds: Path: en.ecn.purdue.edu!pur-ee!mentor.cc.purdue.edu!purdue!tut.cis.ohio-state.edu!snorkelwacker!usc!elroy.jpl.nasa.gov!jarthur!nntp-server.caltech.edu!piglet!madler From: madler@piglet.caltech.edu (Mark Adler) Newsgroups: comp.sys.handhelds Subject: Re: My last post on sorting (sure) for the HP-48SX Message-ID: <1990Apr16.194958.22624@laguna.ccsf.caltech.edu> Date: 16 Apr 90 19:49:58 GMT References: <1990Apr11.045126.5737@laguna.ccsf.caltech.edu> <54098@microsoft.UUCP> Sender: news@laguna.ccsf.caltech.edu Organization: California Institute of Technology, Pasadena Lines: 147 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 \>> \>>