0
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Your algorithm isn't correct $\endgroup$ – Romantic Electron May 17 '17 at 11:10
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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.? $\endgroup$ – Max Koretskyi aka Wizard May 17 '17 at 13:04
  • $\begingroup$ Hint: when you swap(b, i, a[i]), a[ a[i] ]!=a[i] except when i=a[i] $\endgroup$ – VashTheStampede May 17 '17 at 15:33
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.