Given an array A[0..N-1] and a permutation P of 0..N-1 in another array, rearrange A in place so that...

In article <2mdjhm$6ns@elroy.jpl.nasa.gov> ksmith@jpl354.jpl.nasa.gov
(Ken Smith) writes:
>In article <1994Mar19.002614.3512@client10.comlab.ox.ac.uk>
>norvell@comlab.ox.ac.uk (Theo Norvell) writes:
>>
>> Cute.  Here's my attempt  (indexing from 0 and writing  X:=:Y to
>> swap variables)
>>
>> Alg0:   for i : 0..N-1 do
>>                 while P[i] < i do
>>                         P[i] :=: P[P[i]]     <--- (0)
>>                 A[i] :=: A[P[i]]
>>
>>[discussion deleted]
>
>But is your algorithm O(N)?  I suspect that for some initial
>configurations, your while loop is O(N), making your algorithm O(N^2)
>in worst case.

Somewhere in that deleted discussion is the reason it is O(N).  I'll
make it clearer.  Each execution of statement (0) increases the number
of cycles in P by exactly one (by splitting a nontrivial cycle into a
trivial cycle and a remainder).  In pictures it looks like this:
Before:
        j        0    1    2    3    4    5    6
        P[j]     2 <------ 4 <------ 6 <------ 0
                 |                             ^
                 |_____________________________|
                                               i = 6
After P[i] :=: P[P[i]] :
        j        0    1    2    3    4    5    6
        P[j]     0<-+      4 <------ 6 <------ 2
                 |  |      |                   ^
                 |__|      |___________________|
                                               i = 6
Since there is no other statement around to decrease the number of
cycles and because N is an upper bound on the number of cycles in a
permutation, statement (0) can not be executed more that N-C times
where C is the number of cycles originally in P.  In fact it is
executed exactly that many times.

So assuming the comparisons and swaps are O(1), the algorithm is O(N).
(Arguably that is an unreasonable assumption.)

Here is a clearer algorithm based on the same idea:

Alg2
        {Given: P is a permutation}
        {let B = P applied to A}
        var i:=0
        while i not= N
                {invariant: (a) P is a permutation
                        and (b) (Forall j : j<i : P[j] >_ j)
                        and (c) B = P applied to A}
                {variant: 2N - i - the number of cycles in P}
        do
                if P[i] < i
                then
                        A[P[P[i]]] :=: A[P[i]]
                        P[P[i]] :=: P[i]
                else
                        i := i+1
                fi
        od
        {Want to prove: A = B here}

Correctness:
        --The establishment of the invariant
                (a) this is given
                (b) since i=0
                (c) by definition of B
        --The then-part maintains the invariant
                (a) any swap in a permutation gives a permutation
                (b) The only j < i that might be affected is j=P[i].
                    For this j, P'[j] = j (writing P' for the value of
                    P after executing the then-part), so the
                    (b) part remains true.
                (c) Using A' and P' for the values of A and P after the
                    then-part and A and P for the values before:
                    We want to show for all j
                        B[j] = A'[P'[j]]
                    For j = i
                           B[i]
                        =  {from the invariant}
                           A[P[i]]
                        =  {from A[P[P[i]]] := A[P[i] }
                           A'[P[P[i]]]
                        =  {from P[i] := P[P[i]] }
                           A'[P'[i]]
                    For j = P[i]
                           B[P[i]]
                        =  {from the invariant}
                           A[P[P[i]]
                        =  {from A[P[i]] := A[P[P[i]] }
                           A'[P[i]]
                        =  {from P[P[i]] := P[i] }
                           A'[P'[P[i]]]
                    For any other j, no relevant cells are changed.
        --The else-part maintains the invariant.
                (a) and (c) trivially.
                (b) since P[i] >_ i.
        --The then-part decreases the variant
                The swap on P splits a nontrivial cycle into two cycles.
                In particular P'[P[i]] = P[i] and so is a trivial
                cycle, whereas P[i] < i shows that originally cell
                P[P[i]], was a part of a nontrivial cycle.
        --The else-part decreases the variant
                Trivial.
        --The variant can not go below 0.
                Easy.
        --Finally A = B.
                From (b) and i=N, we get that permutation P contains
                no nontrivial cycles, thus P = I (the identity
                permutation).
                   B
                =  {from (c)
                   I applied to A
                =  {I is the identity}
                   A

-- Theo Norvell <norvell@csri.toronto.edu>