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

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?

• Your algorithm isn't correct – Romantic Electron May 17 '17 at 11:10

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' ]


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. :)

• thanks, it's possibile that in one of the next loops that element will be swapped again - I thougt of that that's why I wanted a proof. can you please elaborate on To solve this problem think about swapping a[ ] elements too.? – Max Koretskyi aka Wizard May 17 '17 at 13:04
• Hint: when you swap(b, i, a[i]), a[ a[i] ]!=a[i] except when i=a[i] – VashTheStampede May 17 '17 at 15:33

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.