Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!news.quux.org!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail
From: joes <noreply@example.org>
Newsgroups: comp.theory
Subject: Re: LineSort
Date: Mon, 9 Jun 2025 20:48:17 -0000 (UTC)
Organization: i2pn2 (i2pn.org)
Message-ID: <971c4a9f78840e5c228089b260d30f63b94668c2@i2pn2.org>
References: <1027gln$ofnf$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Injection-Date: Mon, 9 Jun 2025 20:48:17 -0000 (UTC)
Injection-Info: i2pn2.org;
	logging-data="4003712"; mail-complaints-to="usenet@i2pn2.org";
	posting-account="nS1KMHaUuWOnF/ukOJzx6Ssd8y16q9UPs1GZ+I3D0CM";
User-Agent: Pan/0.145 (Duplicitous mercenary valetism; d7e168a
 git.gnome.org/pan2)
X-Spam-Checker-Version: SpamAssassin 4.0.0

Am Mon, 09 Jun 2025 21:37:08 +0100 schrieb Richard Heathfield:

> I have no doubt that I am not the first one here to reinvent several
> wheels (my biggest wheel was AVL tree-balancing, but it's by no means
> the only one).

> Consider a set of n unequal items, such that EITHER Charles > Lisa OR
> Lisa > Charles. You are NOT ABLE to compare two items directly, but you
> are given enough ordered pairings that you can reconstruct the proper
> order of the set.
Which application does this arise from?

> I devised a solution ('LineSort') for this problem, and my question is
> simply whether prior art beat me to it.
> 
> Place the items in arbitrary order. Starting at the back B, work through
> the pairings looking for an item A that is currently ahead of B but
> belongs somewhere behind it, and do this:
> 
> 1. cdefAghijkB
> 2. cdef_ghijkB
> 3. cdefghijkB_
> 4. cdefghijkBA
> 
> Keep going through all your pairings, looking for an item that you can
> dislodge because it belongs behind B; everybody (back to B) shuffles up
> one place, and the dislodged item goes in the place that B vacates.
> 
> When you've run out of pairings, go round again, this time starting with
> the item in front of B.
> 
> Once you're starting at the front, obviously you have to stop. That's
> one pass.
> Make as many passes as you need to until no movements occur throughout
> the pass.
> 
> Clearly this is fairly easy to de-pessimise, but my question is whether
> there is prior art for the general approach.

Looks a lot like bubblesort, a well-known quadratic algorithm.

-- 
Am Sat, 20 Jul 2024 12:35:31 +0000 schrieb WM in sci.math:
It is not guaranteed that n+1 exists for every n.