Path: utzoo!attcan!utgpu!jarvis.csri.toronto.edu!clyde.concordia.ca!uunet!microsoft!alonzo
From: alonzo@microsoft.UUCP (Alonzo Gariepy)
Newsgroups: comp.sys.handhelds
Subject: Quicker quicksort
Message-ID: <9411@microsoft.UUCP>
Date: 12 Dec 89 14:12:13 GMT
Reply-To: alonzo@microsoft.UUCP (Alonzo Gariepy)
Organization: Microsoft Corp., Redmond WA
Lines: 47

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@microsoft