Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!border3.nntp.dca.giganews.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.earthlink.com!news.earthlink.com.POSTED!not-for-mail NNTP-Posting-Date: Fri, 08 Jun 2012 20:26:27 -0500 Message-ID: <4FD2A643.6894@mindspring.com> Date: Fri, 08 Jun 2012 21:26:27 -0400 From: pete Reply-To: pfiland@mindspring.com Organization: PF X-Mailer: Mozilla 3.04Gold (WinNT; I) MIME-Version: 1.0 Newsgroups: comp.lang.c Subject: Re: Breakthrough References: <4FCD273B.5095@mindspring.com> <4fcdb0ef$0$6481$426a74cc@news.free.fr> <4FCEDA85.66BA@mindspring.com> <4FCF56CD.962@mindspring.com> <98pus75mg8q054gcv696u78gvg7gs6h1nk@4ax.com> <4FCFEC9A.C74@mindspring.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 31 X-Usenet-Provider: http://www.giganews.com NNTP-Posting-Host: 4.156.228.6 X-Trace: sv3-fmCXZ58VrLb4bdARkED0v9GrrtmMg5ZXQed0vfOJOrds9E0/QHBbBd/GT9Q1jcuAAZHyo9k9FSwGw0B!o8UdDHb7UuWyrFrDpOHhFDYF89SHlS+s5jVTpKOX7uW1+NBMEl0Z67ljgc0nY6iypfUJjV7OOhuV!fwFtA7Rb X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly X-Postfilter: 1.3.40 X-Original-Bytes: 2138 Xref: csiph.com comp.lang.c:22031 jacob navia wrote: > I am convinced my code would benefit from your critical eye Pete. > > Just download it from > > http://code.google.com/p/ccl/ > > and look at it. > The file listgen.c contains the templated sort function. The first mistake that I noticed, is a common one. In static void QSORT(LIST_ELEMENT **base, size_t num) these two expressions COMPARE_EXPRESSION(loguy,lo) <= 0 COMPARE_EXPRESSION(higuy,lo) >= 0 should be written this way COMPARE_EXPRESSION(loguy,lo) < 0 COMPARE_EXPRESSION(higuy,lo) > 0 to properly address the issue of How to handle keys equal to the partitioning element? See page 4 of http://www.cs.princeton.edu/~rs/talks/QuicksortIsOptimal.pdf How to handle keys equal to the partitioning element? by Robert Sedgewick and Jon Bentley. -- pete