Proving the algorithm that orders an array according to the specified positions 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 &lt; 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?
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. :)