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: Re: Quicker quicksort
Keywords: quicksort, sort, HP28S
Message-ID: <9539@microsoft.UUCP>
Date: 14 Dec 89 23:28:36 GMT
References: <9411@microsoft.UUCP>
Reply-To: alonzo@microsoft.UUCP (Alonzo Gariepy)
Organization: Microsoft Corp., Redmond WA
Lines: 30

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