Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!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: Wed, 11 May 2011 08:39:34 -0500 Message-ID: <4DCA9197.260@mindspring.com> Date: Wed, 11 May 2011 09:39:35 -0400 From: pete Reply-To: pfiland@mindspring.com Organization: PF X-Mailer: Mozilla 3.04Gold (WinNT; I) MIME-Version: 1.0 Newsgroups: comp.unix.programmer,comp.lang.c Subject: Re: Avoiding recursive stack overflow in C on Unix/Linux? References: <2f33e674-b127-4c35-89b5-dcbf564f3aab@h36g2000pro.googlegroups.com> <92rabuF51pU6@mid.individual.net> <87zkmvhyqm.fsf@temporary-address.org.uk> <87aaeui0ic.fsf@temporary-address.org.uk> <3617b15c-1e1e-4353-a96a-0bf4e79881f0@e8g2000vbz.googlegroups.com> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Lines: 52 X-Usenet-Provider: http://www.giganews.com NNTP-Posting-Host: 4.154.223.42 X-Trace: sv3-h6bD3SVK1ZR+BtWw6G8v4Ljy4p8+KhhbR4fSRxukztWpw/cs9LTKsV6PfrZ7lSSd1khdy/+OGnYOgRo!ovKYeNq9F66KgLwHTVtErBnVFLANjRnIMPlp1kpREroCHwnuGfzl8sn43wCNTCSRQpfuHOm/YyRL!2DeOFuO8 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: 3455 Xref: x330-a1.tempe.blueboxinc.net comp.unix.programmer:528 comp.lang.c:3750 robertwessel2@yahoo.com wrote: > > On May 10, 11:16 pm, Keith Thompson wrote: > > Michael Press writes: > > > > [...] > > > > > By the way, qsort(3) has an irremediable security hole. > > > > Can you expand on that? Is it something Unix-specific, or does it > > affect any C implementation (note the cross-post). > > > > (I presume you're aware that qsort() needn't use the Quicksort > > algorithm.) > > I assume he means that Quicksort can go quadratic, and carefully > (mis)designed* input can be an effective denial of service attack. Leapfrogging samplesort is a variation on quicksort which is O(n * (log(n)) * (log(n))) for worst case. http://www.springerlink.com/content/p70564506802n575/ However, I dispute the claim by Eliezer A. Albacea, that "(3) the expected number of data interchanges is slightly higher than that of Quicksort." The expected number of data interchanges is much higher. http://www.mindspring.com/~pfilandr/C/e_driver/ /* BEGIN e_driver.c program output */ Counting comparisons and MOV's for 2 different sorting Sorting arrays of N number of elements. Distribution #1: Shuffled N sqsort NFsort CMPS MOVS CMPS MOVS 1999999 54273473 29450250 39349553 85578207 2000000 55635331 29418642 39348505 85573743 Total cmps sqsort: 109908804 Plain Sedgewick quicksort NFsort: 78698058 Sedgewick loop Leapfrog quicksort Total movs sqsort: 58868892 NFsort: 171151950 /* END e_driver.c program output */ -- pete