Re-ordering a list of fixed-length records in-place

[R.Wieser]

Hello all,

I've got a series of records that I've "sorted" by using a DPA filled with
indices to those records, and use DPA_Sort to sort those indices.

I would now like to re-order the fixed-length records in the order shown by
the DPA, and to make things interresting I would like to have that done
in-place [1].

The thing is that I've been looking at it and I do not see a simple, lineair
approach to it that *doesn't* involve searching for the to-be-swapped-with
record.

Consider the below table. The first colum is the index into the DSA, the
second the index the DSA holds into the actual records, and the third those
records contents.

----|Indx|record content
----+----+------------
0000 0007 I4: 00000384
0001 0000 I4: 00000438
0002 0008 I4: 0000087E
0003 0002 I4: 00000915
0004 0003 I4: 00000B14
0005 0009 I4: 00000CD4
0006 0004 I4: 000011FD
0007 0001 I4: 0000198F
0008 000A I4: 00001B74
0009 0005 I4: 00002245
000A 0006 I4: 000025F8

The DSA list shows the record indices in a sorted order. But how do I now
move the record at index 7 (DSA position 0) to record index 0 without
trashing ther record already there (which should end up at record index 1) ?

Am I looking for something that just can't be done under my 'no searching'
condition ?

[1] My current solution is to copy all the records, use that to copy from
into the origional and finally delete the copy. Which severely limits the
maximum size of the to-be-sorted list of records.

Regards,
Rudy Wieser

[JJ]

Do everything manually.
e.g. move record 3 to record 1 in a 5 records database.

1. Read record 3 data into memory.

2. Update record 3 using record 2 data.

3. Update record 2 using record 1 data.

4. Update record 1 using previously read record 3 data in memory.

It's like the variable value swap trick using a third variable as a
temporary storage.

[R.Wieser]

JJ,

> Do everything manually.
> e.g. move record 3 to record 1 in a 5 records database.

[snip]

Thanks.

First off, I should mention that I have consistently said DSA where I ment
DPA.:-( Luckily it didn't change anything and your answer still applied.
:-)

I guess I was too fixed on doing everything in place (swapping records) to
consider the one-record temporary storage. I did consider following those
record-indices, but just could not figure out how to do the swapping without
messing up records. :-|

I also took your advice quite literally, and wrote the whole thing out. :-)
It turns out that I only need 13 record movements that way. Which is
actually less than I expected.

> It's like the variable value swap trick using a third
> variable as a temporary storage.

:-) I always liked the XOR trick to do that /without/ a temporary variable.

Regards,
Rudy Wieser

[R.Wieser]

JJ,

> I guess I was too fixed on doing everything in place (swapping records)

Thinking a bot more about your solution I realized that my swapping idea
would still work, as it constitutes to "bubbeling" the first record to the
right, moving all other records to the left :

legenda:
x(y,z)
x - DPA index
y - current record index
z - desired record index

'<>' swap action
'..' completed swap action

0(0,7) <> 7(7,1) <> 1(1,0)
0(7,7) .. 7(0,1) <> 1(1,0)
0(7,7) .. 7(1,1) .. 1(0,0)

The problem that I had was that I don't directly see way to also update the
indices stored in the DSA - up until that I realised that I don't need them
after the swapping. Better yet, I can set them to "already swapped"
value, so the next iteration steps see that entries #1 and #7 have already
been processed and must be skipped.

Regards,
Rudy Wieser