How to rearrange an array by indices array (proof)?

Question

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?

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
– gurvinder372, Commented Jun 9, 2016 at 10:44
@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
– gurvinder372, Commented Jun 9, 2016 at 10:49
@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
– deceze ♦, Commented Jun 9, 2016 at 10:51

netoctone · Accepted Answer · 2016-06-09 13:55:12Z

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;
      }
    }
  }
}

edited Jun 9, 2016 at 13:55

answered Jun 9, 2016 at 11:12

netoctone

2312 silver badges5 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Misha Moroshko Over a year ago

Oh, wow! Thanks a lot for presenting a simple counter example!

Misha Moroshko Over a year ago

I created a new question. You might want to add your suggestion there.

Collectives™ on Stack Overflow

How to rearrange an array by indices array (proof)?

1 Answer 1

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related