Path: csiph.com!x330-a1.tempe.blueboxinc.net!usenet.pasdenom.info!weretis.net!feeder4.news.weretis.net!usenet.ukfsn.org!not-for-mail From: Martin Gregorie Newsgroups: comp.lang.java.programmer Subject: Re: Verifying a list is alphabetized Date: Sun, 4 Dec 2011 23:41:49 +0000 (UTC) Organization: UK Free Software Network Lines: 30 Message-ID: References: <722147ec-ab43-4d7c-8b41-32f8705ee7db@i8g2000vbh.googlegroups.com> <4ed9732b$0$294$14726298@news.sunsite.dk> NNTP-Posting-Host: 84.45.235.129 Mime-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit X-Trace: localhost.localdomain 1323042109 320 84.45.235.129 (4 Dec 2011 23:41:49 GMT) X-Complaints-To: usenet@localhost.localdomain NNTP-Posting-Date: Sun, 4 Dec 2011 23:41:49 +0000 (UTC) User-Agent: Pan/0.135 (Tomorrow I'll Wake Up and Scald Myself with Tea; GIT 30dc37b master) Xref: x330-a1.tempe.blueboxinc.net comp.lang.java.programmer:10503 On Sun, 04 Dec 2011 22:11:32 +0000, Tom Anderson wrote: > Tony Hoare, being a scholar and a gentleman, made a strong but measured > claim about it (from the conclusion of [1]): > This was in "Software Tools in Pascal" (Kernighan & Plauger). > I very much doubt that anyone worth listening to has ever made a claim > that quicksort is the fastest in every situation. Pathological cases > have been known for such a long time that to do so would be to court > honorary membership of the Flat Earth Society. > K&P describe shellsort as approximating N**1.5 and say that it averages NlogN but can degrade to n**2 but that worse than NlogN is 'very rare', addinf that to sort an array "just enter 'quick(v, 1, n)' and stand well back". I probably ascribed too much weight to that remark, but OTOH the book says almost nothing about what can degrade its performance. It then goes on to talk about sort-merges which I really related to since I was using a box with 48K RAM at the time and wasn't long away from mainframes with little RAM (multi-user operation with 32 Kwords of RAM: 96 KB equivalent), so all disk sort utilities were of the sort-merge variety - tape sorts were pure multi-way merges preceeded by a collation phase). -- martin@ | Martin Gregorie gregorie. | Essex, UK org |