Proving the algorithm that orders an array according to the specified positions

Question

I have the following task:

Given an array a holding positions and array b holding values, order the elements in the array b according to the positions in the array a. For the input:

a = [3, 0, 1, 2]; 
b = ['a', 'b', 'c', 'd'];

the output should be

[ 'b', 'c', 'd', 'a' ]

I have written a simple algorithm which simply an item into the specified position by swapping:

// a.lenght -1 since the last element will end up in the correct vacant position
for (let i = 0; i < a.length - 1; i++) {
    const position = a[i];
    swap(b, i, position);
}

Although I've tested it and it seems to produce correct results, I can't figure how to prove it works correctly. Can anyone please help with reasoning?

Answer 1

You can't prove a false statement to be true :P

Consider this example:

a = [1, 2, 0]
b = ['a', 'b', 'c']

Output should be:

b = ['c', 'a', 'b' ]

But your algorithm will output:

b = ['c', 'b', 'a']

This because when you swap an element in its "final" position a[i] it's possibile that in one of the next loops that element will be swapped again.

To solve this problem think about swapping a[ ] elements too. :)

Answer 2

Let us run a test case on your algorithm.Let us have two arrays

a=[1,6,3,4,7,2,0,5];
b=[b,g,d,e,h,c,a,f];

As you can see that each element in array a is actually the index if there was an array [a,b,c,d,e,f,g,h]. So the output should produce them in the order a,b,c,d,e,f,g,h

But here's the output of your algorithm At i=0 you get the output

a=[1,6,3,4,7,2,0,5];
b=[g,b,d,e,h,c,a,f];

At i=1

a=[1,6,3,4,7,2,0,5];
b=[g,c,d,e,h,b,a,f];

At i=2 you get the output

a=[1,6,3,4,7,2,0,5];
b=[g,c,e,d,h,b,a,f];

At i=3 you get the output

a=[1,6,3,4,7,2,0,5];
b=[g,c,e,h,d,b,a,f];

At i=4 you get the output

a=[1,6,3,4,7,2,0,5];
b=[g,c,e,h,f,b,a,d];

At i=5 you get the output

a=[1,6,3,4,7,2,0,5];
b=[g,c,b,h,f,e,a,d];

At i=6 you get the output

a=[1,6,3,4,7,2,0,5];
b=[a,c,b,h,f,e,g,d];

At i=7

a=[1,6,3,4,7,2,0,5];
b=[a,c,b,h,f,d,g,e];

If your algorithm was correct then at i=7 the output should be

a=[1,6,3,4,7,2,0,5];
b=[a,b,c,d,e,f,g,h];

So the algorithm doesn't work.