In rexxsort.cmd (50 KB) you'll find several tests of various sort algorithms (Shell sort, heap sort, quick sort, merging sort). Before running any of these tests the script has to be configured by editing a few lines at the top:
| Line | Meaning |
|---|---|
| ABSOLUTE = 0 | If 1 show absolute timings in seconds. |
| VERYSLOW = 0 | If 1 include O(n²) algorithms |
| ALLMERGE = 0 | If 1 include binary and natural merging sort. |
| ALLQUICK = 1 | If 0 include only the best heap and quick sort. |
| ALLSHELL = 1 | If 0 include only the best Shell sort by Knuth. |
| ALL_OEIS = 1 | If 1 include Shell sorts based on OEIS sequences. |
| ALLVALUE = 0 | If 1 include heap and quick sort using value() access. |
| QREXXLIB = 0 | If 1 include external Quercus REXXLIB ARRAYSORT(). |
| REXXUTIL = 0 | If 1 include external Object REXX SysStemSort(). |
| RESERVED = 0 | If 1 include user supplied !SORT(). |
| SEED = random() | Replace a whole number (0..999) to reproduce results. |
With ABSOLUTE = 0 timings are relative to a dummy O(n) procedure (n comparisons plus n moves). The VERYSLOW methods include a QuickSort variant using the first key as pivot element, the desastrous O(n²) effect for already sorted, almost sorted, and almost inverse arrays is shown by TESTS(n). Normally you would set RESERVED = 1 to include whatever actually interesting procedure !SORT at the end of rexxsort.cmd, but the results shown below had no special sort under test.
Finally select one of several tests by replacing the corresponding when 0 then... clause by when 1 then... Actually there are only 5 choices, you can run BASIC(0), BASIC(1), TESTS(n), TESTT(m), or TESTT() without argument.
BASIC(0) is the default if no when 1 then... selection exists. It sorts arrays with 1, 2, etc. upto 19 keys and checks the result against a reference sort. 19 is small enough to show arrays using procedure DEBUG on a line with 80 columns, if you ever have to debug an additional algorithm.
BASIC(1) tries to characterize a sort method using special arrays with sorted, half sorted, inverse, and half inverse keys. The best (fastest) result is used as basis 1.0, and all other results are relative to this basis (factors). You may have to calibrate BASIC on fast machines by editing its line TOP = 5000, if sorting 5000 records takes less than 1 tick, but this problem would be also reported in the result.
Known characteristics are inverse (i.e. the method prefers to sort inverse arrays, typical for heap sort), natural (method prefers to sort already sorted arrays), sequential (method likes sequences of already sorted arrays, typical for natural merging), shuffled (method doesn't like sorted or inverse arrays, typical for a simple quick sort), direct (typical for direct selection), sorted (method prefers only already sorted arrays), orderly (dito less extreme, typical for Shell sort), and none (typical for binary merge, or the number of records is too small to detect another characteristic).
TESTS(n) sorts 4 arrays with n keys. The 1st array contains keys in random order, the 2nd array is already sorted, the 3rd array is almost sorted (one key out of order), and the last array is almost inverse (one key in order). A medium result is shown, where the random array contributes 70% and the three special arrays contribute 10%. Results for TESTS(100000) are shown below.
TESTT(m) sorts arrays with m, 2.5×m, 2.5×2.5×m, etc. keys, as long as the multiplaction by 2.5 yields a whole number. You don't have to compute values for m, simply select an existing case like when 1 then exit TESTT(400) to get five columns for 400, 1000, 2500, 6250, and 15625 keys.
TESTT() without argument shows normally two columns for 59052 resp. 78735 records. With these values I found worst cases for my simple Shell sort: Unlike normal Shell Sorts procedure USORT uses a dynamic (instead of fixed) sequence of distances. The first (now removed) variant of USORT used the formula if K>3 then K=(K%3)+2; else K=1 starting with K=N, where N is the number of records, and REXX operator % an integer division. The actual sequence of distances depends on N, but there are obviously upper and lower bounds. 59052 results in 19686, 6564, 2190, 732, 246, 84, 30, 12, 6, 4, 1, therefore my next attempt was to eliminate even numbers using again the formula K=(K%3)+2 followed by K=K-1 for an even K>4 resp. K=1 for K<5. One worst case for this USORT variant still included in rexxsort.cmd is 78735, i.e. the sequence 26247, 8751, 2919, 975, 327, 111, 39, 15, 7, 3, 1.
To get the results shown below comparing more Shell sorts variants I added 30030 (last primorial below 100000), 50000, 97336 (dito last cube), 99991 (dito last prime), and 100000 to the hardwired TESTT() values. The sequence in Knuth's Shell sort variant is the same as in A003462, the small differences in the result are caused by a multi-tasking system and the code, compare procedures TSORT and S0SORT in rexxsort.cmd, S0SORT upto S6SORT corresponding to EIS (Encyclopedia of Integer Sequences) A0...-sequences are only quick hacks designed to test less than 1,000,000 records. If you really want to sort more than 1,000,000 records use (a) heap sort instead of Shell sort, and (b) a compiled program instead of an interpreted REXX script.
sorting 100000 keys, rel. timing O(n) = 1.230000, seed 171
(70%) (10%) almost almost (100%)
sort methods random sorted sorted invers medium
Hoare QSort 15.171 9.350 9.350 9.886 13.478
treble QSort 12.984 7.919 7.935 8.472 11.521
heap sort 20.203 20.341 20.333 18.642 20.074
simple SSort 30.276 10.659 11.374 17.626 25.159
Shell SSort 37.439 14.911 16.024 18.764 31.177
Knuth SSort 37.602 9.732 10.821 15.504 29.927
A003462 Sort 37.837 9.821 10.894 15.512 30.109
A033622 Sort 25.772 12.862 14.154 17.163 22.459
A036562 Sort 29.577 8.252 9.813 14.789 23.989
A036569 Sort 28.545 11.756 13.098 16.724 24.139
A036564 Sort 66.106 10.886 12.683 19.333 50.564
A055875 Sort 34.154 17.293 18.528 22.618 29.752
A055876 Sort 26.317 12.203 13.146 16.593 22.616
For the results shown above a number like 26.317 means, that a Shell sort based on EIS sequence A055876 took about 32.4 seconds (26.317×1.23) on my busy OS/2 system to sort 100,000 random records for random seed 171. In the results shown below you'll only see relative timings, because the O(n) base 1.23 seconds depends on the number of records.
My interpretation of these results is, that using A055876 could be a good idea, but A033622 is probably better: The formula for A033622 is (relatively) clear and simple. The formula format(1+EXP(1)**(N-2),,0) for A055876 is more complex: You'll always need dubious limits for the precison (REXX NUMERIC DIGITS) and / or for the upper bound of a hardwired table (1,000,000 in S6SORT), and of course REXX has no built-in EXP(1) - but you could use RxShell.
rel. timing based on O(n) 1.0, seed 465 sort methods 30030 50000 59052 78735 97336 99991 100000 Hoare QSort 14.606 14.016 14.803 14.753 14.362 14.651 14.740 treble QSort 12.273 11.887 12.690 12.660 12.307 12.512 12.803 heap sort 18.697 18.097 19.000 19.062 18.575 19.062 19.433 simple SSort 25.000 24.774 31.634 35.010 27.732 28.000 29.764 Shell SSort 31.000 31.065 32.732 34.825 34.795 34.845 34.055 Knuth SSort 29.061 33.274 33.761 34.887 33.276 37.426 35.512 A003462 Sort 28.909 33.161 33.676 34.732 32.858 37.450 35.228 A033622 Sort 23.061 22.500 23.944 24.660 24.150 24.566 24.850 A036562 Sort 25.939 26.000 27.408 28.309 27.874 28.318 29.094 A036569 Sort 25.091 24.645 26.620 26.835 26.614 27.101 27.055 A036564 Sort 58.182 61.694 57.366 67.464 70.220 63.519 73.118 A055875 Sort 28.727 28.952 30.901 32.443 32.055 32.612 33.047 A055876 Sort 23.879 23.113 24.634 25.206 24.669 25.217 25.591
Another interpretation of these results: Use heap sort or maybe treble QSORT (TSORT) instead of any Shell sort. No surprise, but at least it convinced me to delay further efforts to improve the simple SSORT (USORT). The Shell sorts 1 and 2 in the famous REXX Tips & Tricks by B.Schemmer are much worse than all tested versions, and "another sort" is essentially the same as Knuth's Shell sort (A003462 resp. TSORT). The Shell sort in REXXALGO.INF (RXALG130 published 1996) is actually only a bubble sort, it starts with distance 1 doing all the work, but all Shell sorts end with distance 1 for any remaining work.
The name treble QSORT for RSORT is my own invention, its idea is of course not new (probably by Knuth, Hoare, or Wirth): A traditional QSORT uses the M-th key as pivot element in its partition, where M=(L+R)%2 is the Middle of the lower Left and upper Right boundary. If you really want to see the desatrous effects of taking L either edit VERYSLOW = 1 to test a bunch of O(n²) procedures including FSORT, or better copy the FSORT code to !SORT, and select something like TESTS(5000) to see already sorted resp. inverse arrays, the worst cases for FSORT. The mnemonic for FSORT is First choice, i.e. taking the key of the Left boundary as pivot element.
RSORT resp. treble QSORT also determines the Middle M, but then it first sorts the (upto) 3 records with index L, M, and R. A partition with 3 or less records is completely handled in this step. Otherwise the medium key-value (one of the keys with index L, M, R) is taken as pivot element for this partition. Finally the bigger part is pushed for a later QSORT phase, and the smaller part is handled immediately. The bigger part of more than 3 records contains obviously more than 1 record, and the corrsponding check in QSORT is unnecessary in RSORT, compare the end of these procedures.
Now this is all known since about 30 years, but you still find variants of QSORT in the wild with all possible errors, including unnecessary recursion as in RxStemSort() (an external procedure included in good old OS/2 RxUtils.dll) crashing for more than 16384 records with a stack overrun, or even First choice variants like FSORT (see QSORT.ASM in the MS C 6.0 source, it checks the already sorted case explicitly, missing the equally desastrous inverse case).
The recursive QQSORT in REXX Tips & Tricks is quite fast and uses a similar trick to handle small partitions: 8 or less records are sorted directly, bigger parts are handled traditionally, i.e. using the M-th key. Its direct handling is only a bubble sort, this could be improved by using direct selection (see DSORT). The recursion is of course unnecessary, the REXX operations for a stack push and pop are faster:
S = 1 ; SL.1 = 1 ; SR.1 = STEM.0 /* initial stack 1..end */ L = SL.S ; R = SR.S ; S = S - 1 /* pop left L, right R */ S = S + 1 ; SL.S = I ; SR.S = R /* push right part I..R */ S = S + 1 ; SL.S = L ; SR.S = J /* push left part L..J */
Replacing bubble sort by DSORT didn't make QQSORT faster than RSORT, but maybe I'll try harder in a future version of rexxsort.cmd. Please let me know about any algorithm to create a or the worst case (depending on the number of records) for treble QSORT. I'm not yet convinced that using heap sort instead of quick sort is really necessary to avoid desasters. Of course you should always check the source code, and if that's not possible roll your own heap or quick sort.
See also my small collections of REXX links and
scripts, or visit the
EIS page.
Last update: 18 Jul 2003 16:00 by F.Ellermann