****************************************************************************** * DOCUMENTATION FILE FOR QUICK-SORT ROUTINES * * Version 1.01 * * * * October 29, 1990 Kevin P. Jessup * ****************************************************************************** REVISION HISTORY ---------------- Version 1.00 of the QSORT routines was a major memory hog. It was recursive and on each pass created a new copy of the list it was trying to sort. This required about 15 kbytes of free memory to sort a 100 element list. Version 1.01 is still recursive but keeps the list on the stack at all times rather than creating a new copy every time the QST subroutine is entered. The routines that changed with this upgrade are ASORT, QSORT and QST. DESCRIPTION ----------- Hewlett-Packard provides a sorting routine (named SORT) in the programming examples section in volume two of the HP48SX owners manual. Unfortunately, it is based on the bubble sort algorithm which is probably the worst sorting algorithm available. This is an implementation of the quick-sort (QSORT) algorithm. QSORT is a general purpose sorting algorithm that is much faster than bubble sort in almost all situations. The chart below compares sort times for the SORT and QSORT routines for lists of different size. The lists contained real integers sorted in reverse order upon entry to the routines. The routines then sorted them into normal (ascending) order. LIST SIZE SORT (bubble sort) TIME QSORT (quick sort) TIME --------- ----------------------- ----------------------- 5 1.4 seconds 2.4 seconds 10 5.8 5.6 25 65.0 23.1 50 447.0 81.0 For all but the smallest list sizes, QSORT beats SORT. For a list of 50 elements SORT's execution time was 5 times longer than QSORT. An assembly language version would be ideal. This is just "plain" old RPL. Perhaps HP already has a quick sort algorithm buried in the 48SX machine code. If there is one, the appropriate SYSEVAL addresses may eventually become known. [Note: Jim Donnelly's Tool Library contains LSORT and QSORT commands, written in machine language, which are blindingly fast, capable of sorting hundreds of items in less than 1 second! A version of Kevin's program using Donnelly's fast sorting can be found on this disk, called "DS". -jkh-] Six routines are provided in this package. Their byte counts, checksums, inputs, outputs and descriptions are described below. Program listings conform to an HP48SX translation code setting of 3. For conveniance, they are placed in a directory named QSDIR. You may want to move all objects to your home directory for access by other programs. The directory checksum is # 2A9 (hex). The directory consumes 829 bytes of memory. These routines were based on the QSORT routine as described by Kernighan and Ritchie in "The C Programming Language", second edition. Modification was necessary to allow recursion on the HP48SX. ------------------------------------------------------------------------------ Name: QSWAP Bytes: 116 Checksum: # FBA4 (hex) Function: Subroutine used by QST (described below). QSWAP will swap two elements in a list. Listing: \<< \-> a i j \<< 'a' i GET 'a' j GET 'a' i ROT PUT 'a' j ROT PUT a \>> \>> Input: Level 3: list Level 2: element #1 index Level 1: element #2 index Output: Level 1: new list Example: Level 3: { 11 12 13 14 15 16 } Level 2: 1 Level 1: 6 QSWAP Level 1: { 16 12 13 14 15 11 } ------------------------------------------------------------------------------ Name: QST Bytes: 297.5 Checksum: # F84F (hex) Function: The main quick-sort routine. Listing: \<< 0 0 \-> l r i last \<< IF l r < THEN l DUP r + 2 / QSWAP l 'last' STO l 1 + r FOR i IF DUP i GET OVER l GET 4 PICK EVAL 4 PICK XOR THEN 'last' 1 STO+ last i QSWAP END NEXT l last QSWAP l last 1 - QST last 1 + r QST END \>> \>> Input: Level 5: sorting order (0 for normal, 1 for reverse) Level 4: compare routine Level 3: list to be sorted Level 2: left index Level 1: right index Output: Level 3: sorting order Level 2: compare routine Level 1: sorted list The comparisson routine on level 4 is a function that expects inputs on stack levels 1 and 2. It should compare the 2 objects and return a 1 if the object on level 2 is less than the object on level 1. If not, it should return a 0. See the NSORT and ASORT routines below to see how QST is used. Note that QST is recursive. ------------------------------------------------------------------------------ Name: QSORT Bytes: 51 Checksum: # BD12 (hex) Function: Sorts a list of real numbers, strings, etc. Sorts any list of objects that can be compared using the > or < operators. Listing: \<< { < } ROT 1 OVER SIZE QST 3 ROLLD DROP2 \>> Input: Level 2: list Level 1: 0 (normal sort) or 1 (reverse sort) Output: Level 1: sorted list Example 1: Level 2: { 1 2 3 4 9 8 7 6 5 } Level 1: 1 (reverse sort) QSORT Level 1: { 9 8 7 6 5 4 3 2 1 } Example 2: Level 2: { "ZZZ" "ABC" "abc" "CCB" "CCA" } Level 1: 0 (normal sort) QSORT Level 1: { "ABC" "CCA" "CCB" "ZZZ" "abc" } ------------------------------------------------------------------------------ Name: ASORT Bytes: 66 Checksum: # E13E (hex) Function: Same as QSORT above except all objects in the list are compared as if they were strings (alphabetically). Listing: \<< \<< \->STR SWAP \->STR \>= \>> ROT 1 OVER SIZE QST 3 ROLLD DROP2 \>> Example 1: Level 2: { 123 1 11 1000 22 } Level 1: 0 ASORT Level 1: { 1 1000 11 123 22 } Example 2: Level 2: { QSWAP QST ASORT QSORT NSORT } Level 1: 0 ASORT Level 1: { ASORT DSORT QSORT QST QSWAP } The above are all the routines necessary for the QSORT package. A utility for sorting HP48SX directories is described below. It uses the ASORT routine just described. ============================================================================== File name: VLPARSE Bytes: 184 Ckecksum: # 9754 (hex) Function: VLPARSE will take a list of variables and either delete or save all variables of a given type from that list. Listing: \<< { } \-> l t d n \<< IF l SIZE DUP THEN 1 SWAP FOR i 'l' i GET IF VTYPE t == d XOR THEN n 'l' i GET 1 \->LIST + 'n' STO END NEXT ELSE DROP END n \>> \>> Inputs: Level 3: LIST of variables Level 2: object type (see page 97 of manual) Level 1: 0 (to save the variables) or 1 (to delete the variables) Outputs: Level 1: The parsed LIST. Example 1: 1) From your top level directory, execute the VARS command. 2) A list of variables should now be on the stack. 3) Enter 15 on the stack (this specifies a directory object). 4) Enter 0 on the stack (this tell VLPARSE to save all occurences of the object). 5) Execute VLPARSE. 6) A list of all directory objects remains on the stack. Example 2: Get a list of all variables in the current directory that do NOT contain PROGRAM objects. 1) Execute the VARS command. 2) Enter the real number 8 (specifies a program object). 3) Enter the real number 1 (delete variables of specified type). 4) Execute VLPARSE. 5) A list of all variables in the current directory that are NOT program objects remains on the STACK. If all objects in the current directory WERE program objects, the list is empty. ------------------------------------------------------------------------------ File name: DSORT (Directory SORT) Bytes: 98.5 Ckecksum: # E97B (hex) Function: DSORT will sort a directory alphabeticly. Sub-directores will be sorted first, followed by all other objects. Note that DSORT calls VLPARSE and ASORT as subroutines. Listing: \<< VARS 15 0 VLPARSE 0 ASORT VARS 15 1 VLPARSE 0 ASORT + ORDER \>> Inputs: None Outputs: The current directory is sorted. The actual variables within the subdirectories are NOT sorted. *************************************************************************** Support the HP48SX BBS shareware concept by sending a couple-a-bucks to the author OR posting your own USEFULL programs to the HP48SX BBS. Kevin Jessup 9118 N. 85th St. Milwaukee, WI 53224 ***********************************[END]***********************************