Article View: rec.games.programmer
Article #1025Re: Advice needed for fastest sort algorthm
From: Steven C. Dollins
Date: Sun, 08 Nov 1992 03:37
Date: Sun, 08 Nov 1992 03:37
24 lines
1559 bytes
1559 bytes
In article <1992Nov8.012628.23338@menudo.uh.edu> libh@Jane.UH.EDU writes:
The bubble sort takes N! (# factorial) steps, rather than N*N
steps. A BIG difference. But as pointed out, the quicksort is the
easiest to implement since it is in C libraries. Why reinvent the
wheel. If that isn't quick enough then I would check out Knuth's 'Art
of Programming' Vol. 3 since it is pretty much only about sorting.
[Obnoxiously wide .sig deleted]
The bubble sort takes, in the asymptotic limit, 1/2 N^2 time, which is
nowhere NEAR N!. Where on earth did you get that idea?
Quick sort is O(n log n) on average, O(n^2) in the worst case. With a
good randomized quick sort, the worst case will be extremely unlikely.
- Steven Dollins
Brown Computer Graphics Group scd@cs.brown.edu
--
"This could only be USENET. Nowhere else in the known universe
would you find such a mind-boggling ratio of ill-informed
conjecture to actual fact."
-- parghi@cs.uiuc.edu (Amit Parghi)
Technical Details
Message-ID:
<SCD.92Nov7223729@nevar.cs.brown.edu>Path:
arc1-ca.pugleaf.net!sparky!uunet!brunix!doorknob!scdReferences:
<6759@news.duke.edu>,<BxD5pt.DyI@news.cso.uiuc.edu> <1992Nov8.012628.23338@menudo.uh.edu>Show Full Headers
Complete Article Headers
Newsgroups: rec.games.programmer Path: arc1-ca.pugleaf.net!sparky!uunet!brunix!doorknob!scd From: scd@cs.brown.edu (Steven C. Dollins) Subject: Re: Advice needed for fastest sort algorthm In-Reply-To: libh@Jane.UH.EDU's message of Sun, 8 Nov 1992 01:26:28 GMT Message-ID: <SCD.92Nov7223729@nevar.cs.brown.edu> Sender: news@cs.brown.edu Organization: Dept. of Computer Science, Brown University References: <6759@news.duke.edu>,<BxD5pt.DyI@news.cso.uiuc.edu> <1992Nov8.012628.23338@menudo.uh.edu> Date: Sun, 8 Nov 1992 03:37:29 GMT Lines: 24