Article View: demon.ip.developers
Article #134Re: news
From: John F Hall
Date: Mon, 10 Aug 1998 00:00
Date: Mon, 10 Aug 1998 00:00
16 lines
1371 bytes
1371 bytes
In article <902681235.11119.0.nnrp-01.c30b3753@news.demon.co.uk>, Tony Finch <fanf@demon.net> wrote: >shellsort != bubblesort -- it's far more efficient, although (IIRC) >no-one has yet proven exactly how efficient it is... I once came across a shellsort run that took a *very* long time. Investigation showed that it was sorting power-of-2 items, so that each iteration failed to mix the previous interations, effectively giving bubblesort time. I modified the sort so that the first iteration always reduced the number to power-of-2-minus-1, rather that just halving. That meant that subsequent halving always gave two co-prime numbers guaranteeing maximum mixing. -- John F Hall
Technical Details
Message-ID:
<6qmu6m$cbh$1@avondale.demon.co.uk>Path:
arc1-ca.pugleaf.net!unknown!not-for-mailReferences:
<vSBoABAkL9t1EwwM@ubik.demon.co.uk> <gUI7zNADfCz1EABV@turnpike.com> <87lnozuhh7.fsf@loki.wkstn.nix> <902681235.11119.0.nnrp-01.c30b3753@news.demon.co.uk>Show Full Headers
Complete Article Headers
X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 10bb05,ea300c1ef086cd2b X-Google-Attributes: gid10bb05,public From: jfhall@avondale.demon.co.uk (John F Hall) Subject: Re: news Date: 1998/08/10 Message-ID: <6qmu6m$cbh$1@avondale.demon.co.uk> X-Deja-AN: 379823995 X-NNTP-Posting-Host: avondale.demon.co.uk:158.152.19.72 References: <vSBoABAkL9t1EwwM@ubik.demon.co.uk> <gUI7zNADfCz1EABV@turnpike.com> <87lnozuhh7.fsf@loki.wkstn.nix> <902681235.11119.0.nnrp-01.c30b3753@news.demon.co.uk> X-Trace: news.demon.co.uk 902782069 nnrp-01:25510 NO-IDENT avondale.demon.co.uk:158.152.19.72 Newsgroups: demon.ip.developers X-Complaints-To: abuse@demon.net