madler@piglet.caltech.edu (Mark Adler) (04/11/90)
Here posted are somewhat improved versions of SORT and QPART. These
represent about a 2% increase in speed from the previous version (I
couldn't resist even such a trivial improvement). The change was
simply to test the size of the list before calling QPART, both from
SORT, and from the two places in QPART itself. The comments are also
a little more complete. Enjoy.
Mark Adler
madler@tybalt.caltech.edu
%%HP: T(3)A(R)F(.);
@ SORT crc #10B7h length 141
@
@ by Mark Adler 10 Apr 1990
@
@ 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. See the comments
@ in QPART.
@
@ The sort will be fastest if the list being sorted was recalled from a
@ global variable. This avoids garbage collection on the objects in
@ the list when they are on the stack. It will also speed the sort to
@ disable last args with a "-55 SF".
@
@ To sort objects other than reals or strings, change the ">" in
@ "PICK >" to the appropriate code and modify QPART in the same way
@ (see the comments in QPART).
@
\<< OBJ\-> DUP \-> n @ put list on stack
\<<
@
@ if size > 20, do quicksort
@
IF DUP 20 > THEN 2 QPART n END @ partition is [1] to [n]
@
@ do insertion sort on what remains
@
2 SWAP FOR j @ starting with j=2, insert [j]
j ROLL j 2 + @ [1]..[j-1] is sorted, get [j]
WHILE DUP2 PICK > REPEAT 1 - END @ find where [j] goes
2 - ROLLD @ put [j] there
NEXT
n \->LIST @ convert back to list
\>>
\>>
%%HP: T(3)A(R)F(.);
@ QPART crc #7BCCh length 419.5
@
@ by Mark Adler 10 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.
@
@ 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 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 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
\>>
\>>