Article View: rec.games.programmer
Article #1199Re: Advice needed for fastest sort algorthm
From: David &
Date: Fri, 13 Nov 1992 16:23
Date: Fri, 13 Nov 1992 16:23
12 lines
1214 bytes
1214 bytes
Tommy Nordgren (f85-tno@nada.kth.se) wrote: : Not only has quicksort bad worst-case performance, but this worst : case WILL occur in the considered application, since the list will always be : nearly sorted after any reasonable wievpoint movement. There is a simple fix called median-of-three that eliminates this particular worse case. The partition is picked from the median of the first,last, and middle in the set to be sorted. Thus in already sorted lists the partition is picked from the middle, which is the ideal for Quicksort. -- neves@ils.nwu.edu Institute for the Learning Sciences, 1890 Maple, Evanston Il 60201
Technical Details
Message-ID:
<1992Nov13.162353.7316@ils.nwu.edu>Path:
arc1-ca.pugleaf.net!sparky!uunet!utcsri!newsflash.concordia.ca!garrot.DMI.USherb.CA!uxa.ecn.bgu.edu!news.ils.nwu.edu!aristotle.ils.nwu.edu!nevesReferences:
<1992Nov12.195155.14124@kth.se>Show Full Headers
Complete Article Headers
Newsgroups: rec.games.programmer Path: arc1-ca.pugleaf.net!sparky!uunet!utcsri!newsflash.concordia.ca!garrot.DMI.USherb.CA!uxa.ecn.bgu.edu!news.ils.nwu.edu!aristotle.ils.nwu.edu!neves From: neves@aristotle.ils.nwu.edu (David &) Subject: Re: Advice needed for fastest sort algorthm Message-ID: <1992Nov13.162353.7316@ils.nwu.edu> Sender: usenet@ils.nwu.edu (Mr. usenet) Nntp-Posting-Host: aristotle.ils.nwu.edu Organization: The Institute for the Learning Sciences X-Newsreader: Tin 1.1 PL5 References: <1992Nov12.195155.14124@kth.se> Date: Fri, 13 Nov 1992 16:23:53 GMT Lines: 12