Path: utzoo!attcan!uunet!zephyr.ens.tek.com!uw-beaver!cornell!rochester!pt.cs.cmu.edu!o.gp.cs.cmu.edu!andrew.cmu.edu!vd09+ From: vd09+@andrew.cmu.edu (Vincent M. Del Vecchio) Newsgroups: comp.sys.mac.programmer Subject: Re: fastqsort.c -- 3 times faster than THINK C's qsort() Message-ID: Date: 26 Sep 90 02:10:16 GMT References: <60123@iuvax.cs.indiana.edu> <1990Sep25.044455.3039@Neon.Stanford.EDU> <7739@ucdavis.ucdavis.edu>, <60287@iuvax.cs.indiana.edu> Organization: Carnegie Mellon, Pittsburgh, PA Lines: 24 In-Reply-To: <60287@iuvax.cs.indiana.edu> > Excerpts from netnews.comp.sys.mac.programmer: 25-Sep-90 Re: fastqsort.c > -- 3 times .. Haydn Huntley@copper.ucs (2015) > The way to calculate the possibility of that algorithm receiving it's > worst case input is 1/N!, where N is the number of items in the list > to be sorted. If N > 10, that number is *vanishingly* small, much > smaller than the chance of being struck by lightning, etc., etc. If N > <= 10, then that randomized algorithm will sort the data so quickly, > that it doesn't much matter whether it hits it's worst case or not! The absolute worst case may only occcur with a probability of 1/N!, but there are other cases which are very close to worst case in performance (e.g. take the worst case and move around a small fraction of the numbers) and that makes the 1/N! analysis seem rather irrelevant. Note that this is not to say that your algorithm doesn't do a good job. +----------------------------------------------------------------------------+ | Vincent Del Vecchio \ Disclaimer: Views expressed are not necessarily | | Box 4872 \ those of any person/group I am associated with. | | 5125 Margaret Morrison St.\ UUCP: {uunet,harvard}!andrew.cmu.edu!vd09 | | Pittsburgh, PA 15213 \ BITNET: vd09+%andrew@cmuccvma.bitnet | | (412) 268-4441 \ Internet: vd09+@andrew.cmu.edu | +----------------------------------------------------------------------------+