home *** CD-ROM | disk | FTP | other *** search
- Path: sparky!uunet!charon.amdahl.com!pacbell.com!sgiblab!zaphod.mps.ohio-state.edu!pacific.mps.ohio-state.edu!linac!att!ucbvax!ucdavis!hamlet.ucdavis.edu!f110019
- From: f110019@hamlet.ucdavis.edu (Julian Burger)
- Newsgroups: rec.games.programmer
- Subject: Re: Advice needed for fastest sort algorthm
- Message-ID: <19387@ucdavis.ucdavis.edu>
- Date: 18 Nov 92 21:46:29 GMT
- References: <1992Nov11.043526.26732@netcom.com> <1992Nov11.161052.5552@panther.mot.com> <1992Nov12.154308.4827@cbnews.cb.att.com>
- Sender: usenet@ucdavis.ucdavis.edu
- Organization: Computing Services, UC Davis
- Lines: 26
-
- In article <1992Nov12.154308.4827@cbnews.cb.att.com> nak@cbnews.cb.att.com (neil.a.kirby) writes:
- >In article <1992Nov11.161052.5552@panther.mot.com> asu@panther4.panther.mot.com (Russ Trotter) writes:
- >>I hate to jump on this seemingly runaway train but....
- >>
- >>In one of my classes, I remember the teacher saying that it
- >>had been proven that O(n log n) was the best one could do
- >>for _comparison_ based sorting... Is this a more correct assertion?
- _single key comparison_...
-
- [... lots of stuff on sorting condensed into the following character: % ...]
-
- >*THE* thing to remeber in all of this is that order notation is applicable
- >only as n rises. Bubble sort has a very low overhead, it works well on
- >semi-sorted data, and most programmers can write it correctly. That third
- >point should not be ignored. Classical quicksort has to be modified to
- >keep from choking (O n*n )on sorted data.
-
- The *OTHER* thing to remember is that the order O(xxx) of the algorithm
- represents the number of OPERATIONS required to do the sorting. The
- operations for each algorithm are not necessarily the same. For instance, a
- single key comparison is a simple inequality test, but for a radix sort you
- need to isolate each digit of the radix and work with that.
-
- >Neil Kirby
-
- JB @ UCD
-
