Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!swrinde!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!cica!iuvax!copper!huntley
From: huntley@copper.ucs.indiana.edu (Haydn Huntley)
Newsgroups: comp.sys.mac.programmer
Subject: Re: fastqsort.c -- 3 times faster than THINK C's qsort()
Message-ID: <60332@iuvax.cs.indiana.edu>
Date: 26 Sep 90 02:29:59 GMT
References: <60123@iuvax.cs.indiana.edu> <1990Sep25.044455.3039@Neon.Stanford.EDU> <7739@ucdavis.ucdavis.edu> <7004@tekig5.PEN.TEK.COM>
Sender: news@iuvax.cs.indiana.edu
Organization: Indiana University, Bloomington IN.
Lines: 58

In article <7004@tekig5.PEN.TEK.COM> philj@tekig5.PEN.TEK.COM (Phil K Jansen) writes:
| Our Algorithms class demonstrated that the insertion sort was faster
| for less than ~25 elements.  This is because you start to notice quickSort's
| subroutine overhead for each element actually moved.
| 
| So what you really want to do is CHANGE THE SORT ALGORITHM for small lists.
| This will improve worst-case behavior to near the insertion-sort level.
| 
| hyperQuickSort(arguments) {
| 	if(numElements > 25)
| 	    quickSort(arguments);
| 	        /* recursively calls hyperQuickSort() -- twice */
| 	else
| 	    insertionSort(arguments); /* good ol' dumb insertion sort */
| }

Actually, the best general purpose sorting algorithm I could come up
with used just this technique, however it was only 4 times faster than
THINK's, and several times longer than fastQsort(), so I didn't think
many people would be interested in it.  If anyone is interested, I'd
be delighted to mail you the collection of sorting algorithms and the
code I wrote for timing, testing, and comparing them all.  It's
fun to play around with sorts, and instructive too!  :-)

Perhaps sorting algorithms are an emotional issue -- so many people
have posted and mailed trying to tell me that randomizing the
algorithm doesn't change it's worst case behavior.  Technically, they
are not mistaken, the worst case behavior of fastQsort is N*N, but the
chance of observing that behavior is tiny.  If you perform one sort per
second for the rest of your life, and you are sorting arrays of 1024
elements, I think it is incredibly unlikely that you will observe
fastQsort exhibiting worst case behavior before pass on to elsewhere.
A person may live for 3 billion seconds, but 1024! is much larger!
Fifty factorial is more than 3x10^64, and most calculators can't do
more than 69!.

| 
| I expect most of the speedup came from the asm{} statements for the swaps.
| 

Some speedup came from fixing their assembler code.  The big wins came
from randomizing the algorithm (to avoid worst case behavior on common
cases), and from using pointers instead of array indexing.

| As Haydn said, he did get 3x improvement from optimizing the algorithm.  But
| he also made it non-portable.  Of course we're all 68000 Mac users here, so
| maybe portability is less of an issue.  I need it, though.
|

If you'd like a portable algorithm, just convert memSwap() to C -- the
equivalent C code is in comments just to the right of the assembler.




;;  *****************************************************
;;  *  Haydn Huntley    huntley@copper.ucs.indiana.edu  *
;;  *****************************************************