Re: LineSort

On 09/06/2025 21:48, joes wrote:

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?

brainbashers.com :-)
Jill finished after Helen but beat Alan. Bob lost out to Derek but was faster than Tina... etc etc etc.

 

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.

Yes, it certainly has the bubbling quality from which bubblesort gets its name, but bubblesort is allowed to compare two arbitrary items directly, which is not possible here.
--
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within