alonzo@microsoft.UUCP (Alonzo Gariepy) (12/12/89)
Here is a quicker quicksort:
QSORT [B42D]
<< LIST-> QST >>
QST [5BC0]
<<
IF DUP 2 < ; X is 2 in this case
THEN ->LIST ; sort list with length < X
ELSE -> n
<< n RAND * CEIL ROLL ; choose random partition
n 3 + ; size of left sublist biased by 3
2 n START
ROT 3 DUPN SWAP ROLLD > - ; this is tricky
NEXT
3 - n OVER - OVER 2 + ROLLD ; package up sublists and partition
1 - SWAP OVER 2 + ROLLD ; value
QST SWAP + ; sort left sublist and add pttn value
OVER 2 + ROLLD QST + ; sort right sublist and add it too
>>
END
>>
The highly optimized partition loop makes this quicksort much faster
than that previously posted. The use of RAND in choosing the partition
value all but eliminates the variance in speed so that the likelihood
of worst-case performance is virtually nil.
Typical sort time for a list of 50 real numbers is less than 15 seconds
whether or not the list is already sorted. The sort is non-deterministic
because different partition values are chosen each time.
I experimented with using a simple exchange sort for sublists with three
elements or less, but the improvement was only 10%. You may want to try
an alternative sort (insertion or selection) for sublists with less than
X elements. You would do this by changing the beginning of QST to:
<<
IF DUP X <
THEN ALTSRT
Where ALTSRT has the same inputs and outputs as the ->LIST command but
returns the elements in sorted order. I would expect as much as a 20%
speedup in this way.
Alonzo Gariepy
alonzo@microsoftalonzo@microsoft.UUCP (Alonzo Gariepy) (12/15/89)
In article <9411@microsoft.UUCP> I wrote: > QST [...] > ... > n RAND * CEIL ROLL ; choose random partition > ... > The use of RAND in choosing the partition value all but eliminates the > variance in speed so that the likelihood of worst-case performance is > virtually nil. If you don't need to avoid worst-case performance for all possible lists, you can speed this up by taking into account the characteristics of the lists you will be sorting. For most applications, lists will be either partially sorted, sorted in reverse order, or completely random. If you always choose the middle element of a sublist as the partition value you get optimum results for already sorted lists and eliminate overhead of the RAND function. To do this, replace the line shown above to: n 2 / ROLL ; choose middle element for partition This will reduce typical sort times by more than 20%. A random list of 50 real numbers sorts in about 13 seconds. An already sorted list takes 11.5 seconds. If you work at it, you can construct a list that takes 63 seconds to sort. This is twice as fast as the elegant sort originally posted because, in the worst case, most of the time is spent in the partitioning loop. Alonzo Gariepy alonzo@microsoft