1

Given an array arr and an array of indices ind, the following algorithm rearranges arr in-place to satisfy the given indices:

function swap(arr, i, k) {
  var temp = arr[i];
  arr[i] = arr[k];
  arr[k] = temp;
}

function rearrange(arr, ind) {
  for (var i = 0, len = arr.length; i < len; i++) {
    if (ind[i] !== i) {
      swap(arr, i, ind[i]);
      swap(ind, i, ind[i]);
    }
  }
}

For example:

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [ 4,   0,   5,   2,   1,   3 ];

rearrange(arr, ind);

console.log(arr); // => ["B", "E", "D", "F", "A", "C"]

What's the most convincing way to prove that the algorithm works?

deceze
  • 510,633
  • 85
  • 743
  • 889
Misha Moroshko
  • 166,356
  • 226
  • 505
  • 746
  • Write a bunch of test cases and show that they pass...?! – deceze Jun 09 '16 at 10:41
  • @deceze I'm looking for a more theoretical proof of the algorithm – Misha Moroshko Jun 09 '16 at 10:42
  • 2
    why do you think that this algorithm works at first place? Shouldn't the output be `["E", "A", "F", "C", "B", "D"]` on the basis of indices? – gurvinder372 Jun 09 '16 at 10:44
  • 1
    @gurvinder372 ...? Why? – deceze Jun 09 '16 at 10:47
  • 1
    @deceze Unless I have missed something, rearranging `["A", "B", "C", "D", "E", "F"]` as per `[4, 0, 5, 2, 1, 3]` should give `["E", "A", "F", "C", "B", "D"]` right? Since `E` is at the fourth index and `A` is at 0th index..? – gurvinder372 Jun 09 '16 at 10:49
  • 2
    @gurvinder372 Not sure what logic you're applying there... the second array seems to contain the desired indices for values of the same key in the first array. `arr[0]` should go to the index `ind[0]`, which is `4`, which means 'A' should go to position `4`. – deceze Jun 09 '16 at 10:51
  • @deceze: Indeed, but I didn't get the logic as well before reading your last comment (so thanks for that). Perhaps the tile "rearrange an array **by indices**" is slightly confusing to be honest (or should be better explained in the question itself) – briosheje Jun 09 '16 at 10:53
  • Here is another solution for this problem with `reduce` and `sort` https://jsfiddle.net/Lg0wyt9u/957/ – Nenad Vracar Jun 09 '16 at 10:56
  • @deceze got it now, I was applying the indices in a reverse manner. Thanks for clarifying. – gurvinder372 Jun 09 '16 at 11:00

1 Answers1

4

This algorithm does not work, it's enough to show a counter-example:

var arr = ["A", "B", "C", "D"];
var ind = [  2,   3,   1,   0];

rearrange(arr, ind);
console.log(arr); // => ["C", "D", "A", "B"]

A working alternative may be

function swap(arr, i, k) {
  var temp = arr[i];
  arr[i] = arr[k];
  arr[k] = temp;
}

function rearrange(arr, ind) {
  for (var i = 0, len = arr.length; i < len; i++) {
    if (ind[i] !== i) {
      swap(arr, i, ind[i]);
      swap(ind, i, ind[i]);
      if (ind[i] < i) {
        i = ind[i]-1;
      }
    }
  }
}
netoctone
  • 231
  • 2
  • 5