Path: csiph.com!x330-a1.tempe.blueboxinc.net!newsfeed.hal-mli.net!feeder3.hal-mli.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: Sun, 04 Dec 2011 17:32:29 -0600
Date: Sun, 04 Dec 2011 15:32:21 -0800
From: Patricia Shanahan <pats@acm.org>
User-Agent: Mozilla/5.0 (Windows NT 5.2; WOW64; rv:8.0) Gecko/20111105 Thunderbird/8.0
MIME-Version: 1.0
Newsgroups: comp.lang.java.programmer
Subject: Re: Verifying a list is alphabetized
References: <722147ec-ab43-4d7c-8b41-32f8705ee7db@i8g2000vbh.googlegroups.com> <jb5k7n$g4u$1@dont-email.me> <4ed9732b$0$294$14726298@news.sunsite.dk> <jbd5k5$86c$1@dont-email.me> <b5sld7ltif6oi2tke3q2fkr5vnr2cc6nkc@4ax.com> <jbfpru$ksi$2@localhost.localdomain> <WPidnXX0kcoMSEbTnZ2dnUVZ_q6dnZ2d@earthlink.com> <ZrRCq.5933$cN1.371@newsfe12.iad>
In-Reply-To: <ZrRCq.5933$cN1.371@newsfe12.iad>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Message-ID: <jY6dnVhvedWQnkHTnZ2dnUVZ_r2dnZ2d@earthlink.com>
Lines: 15
X-Usenet-Provider: http://www.giganews.com
NNTP-Posting-Host: 70.230.194.31
X-Trace: sv3-N22sWZiqb0Al9eajxga0x5/fG6mMIsw+sao8rbWjJYljNEAgOabY22ZMvd3SZMK9pESQoCEAJ4N1TeQ!FPocvi0y5Zjov7GUrVOzV2JYcjht9gyRS+NOglm2W2lZGJAh/SxboX9UzfBlYjsyFWDv87qVs3Qe!Xvd3yQhFMsHY/D6iE/hB+c2Nxq0m/hze/nTEPopPMKec6w==
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: 2162
Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:10502

On 12/4/2011 1:17 PM, Daniel Pitts wrote:
> On 12/4/11 12:18 PM, Patricia Shanahan wrote:
...
> I remember reading a paper online a while back which showed that it was
> possible to create a comparison specifically designed to thwart Quick
> Sort. Not sure why anyone would want to do that in a real life
> situation, but the paper showed that it could cause common QS
> implementations to always approach n^2.

One practical use of such a data set would be to bring home to algorithm
design students and programmers choosing algorithms the difference
between "average O(n log(n) time" and "O(n log(n)) time", which by
default means a bound on the maximum time across all input sets.

Patricia