How to sort an array in-place given an array of target indices?

Question

How would you sort a given array arr in-place given an array of target indices ind?

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

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

rearrange(arr, ind);

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

I tried the following algorithm, but it fails on the second example above.

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

How would you solve this in O(n) time and O(1) extra space?

Could you provide a proof that your algorithm works?

Note: This question looks similar to this one, but here mutating ind is allowed.

Why do you ask the same question [again](http://stackoverflow.com/questions/37460524/how-to-rearrange-an-array-by-indices-array) and [again](http://stackoverflow.com/questions/37723626/how-to-rearrange-an-array-by-indices-array-proof)? — trincot, Jun 09 '16 at 12:00
@trincot If you read carefully, you'll see that the requirements in the other questions you linked are slightly different. I added a note at the end of the question to make it clear. — Misha Moroshko, Jun 09 '16 at 12:12

OB1 · Accepted Answer · 2016-06-09T12:18:53.733

The algorithm fails because it has only one loop over the indices of your list.

What happens in your algorithm is this :

i=0 -> ["A", "B", "C", "D"] , [ 2,   3,   1,   0 ]
i=1 -> ["C", "B", "A", "D"] , [ 1,   3,   2,   0 ]
i=2 -> ["C", "D", "A", "B"] , [ 1,   0,   2,   3 ]
i=3 -> ["C", "D", "A", "B"] , [ 1,   0,   2,   3 ]

Note how by the first swap, 1 is in position 0 and you will not visit it again unless you swap it with 0, which does not happen in this example.

What your algorithm misses is an internal loop that runs through sub-cycles of indexes. Try replacing the if by while in rearrange:

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

Note on complexity: although this is a double loop, complexity does not change because at each swap, one element is correctly placed, and each element is read at most twice (once through the cycling, once though the for loop).

Note on proof: I will not do a complete proof of this algorithm here, but I can give leads. If ind is a permutation, then all elements belong to closed permutative sub-cycles. The while loop ensures that you're iterating entire cycles, the for loop ensures that you're checking for every possible cycle.

Seems correct to me. You use the index array to mark an element / cycle as being processed and thus can skip those, reducing complexity from O(n^2) for immutable inputs to an optimal O(n). — le_m, Jun 10 '16 at 00:53

Nina Scholz · Answer 2 · 2016-06-09T12:26:06.967

I suggest to swap until the same index is reached and then take the next outer index.

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

function rearrange(arr, ind) {
    var i = arr.length;
    while (i--) {
        while (ind[i] !== i) {
            swap(arr, i, ind[i]);
            swap(ind, i, ind[i]);
        }
    }
}

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

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

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

score 0 · Answer 3 · answered Jun 09 '16 at 11:44

0

How would you solve this in O(n) time?

By simply using a temporary array and iterating the arrays twice, you can reduce it to O(n)

function rearrange(arr, ind) 
{
  var temp = [], len = arr.length;
  //first re-arrange in a new array
  for(var counter = 0; counter < len; counter++)
  {
     temp[ind[counter]] = arr[counter];
  }  
  //copy the values as per new indices from temp
  for(var counter = 0; counter < len; counter++)
  {
     arr[counter] = temp[counter];
  }  
}

answered Jun 09 '16 at 11:44

gurvinder372

66,980
10
72
94

Sorry, I forgot to mention that extra space allowed is O(1). – Misha Moroshko Jun 09 '16 at 11:53
@MishaMoroshko sorry, didn't get what is meant by `extra space` – gurvinder372 Jun 09 '16 at 14:03

score 0 · Answer 4 · 2016-06-10T00:39:56.967

If you satisfied with doing that with less complexity method, then there is a one:

Make a new array with length equal to arr length and with empty objects
splice the new array by the index of ind[i], remove 1 object , and replace it with arr[i]
Equalize the old array(arr) with the new one

window.onload = function () {
    
    'use strict'; 
 
 var arr = ["A", "B", "C", "D", "E", "F"];
 var ind = [ 4,   0,   3,   2,   1,   5 ];
 var temp = [];

 for (var i = 0; i < arr.length; i++) {
     temp[i] = '';
 }

 for (var v = 0; v < arr.length; v++) {
     temp.splice(ind[v], 1, arr[v]);
 }
 
 arr = temp;
 console.log(arr);
};

AnotherGeek · Answer 5 · 2016-06-09T13:06:08.430

0

I suggest that you return your result in a new array

   function createArray(arr, ind) {
        var result = [];
        for (var i = 0, len = arr.length; i < len; i++) {
            result.push(arr[ind[i]]);
        }
        return result;
    }

This is in O(n) time

var arr = ["A", "B", "C", "D", "E", "F"];
var ind = [4, 0, 5, 2, 1, 3];
console.log(createArray(arr,ind))

edited Jun 09 '16 at 13:06

answered Jun 09 '16 at 11:54

AnotherGeek

874
1
6
24

While this code snippet may solve the question, [including an explanation](https://meta.stackexchange.com/questions/114762/explaining-entirely-code-based-answers) really helps to improve the quality of your post. Remember that you are answering the question for readers in the future, and those people might not know the reasons for your code suggestion. Please also try not to crowd your code with explanatory comments, this reduces the readability of both the code and the explanations! – Box Box Box Box Jun 09 '16 at 12:47

score 0 · Answer 6 · edited May 23 '17 at 10:34

There is a lot of discussion on a similar problem In-place array reordering?

The difference is that in original problem ind[i] is a required index for element arr[i], while in the similar problem i is a required index for element arr[ind[i]]

Going back to the original algorithm, 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;
      }
    }
  }
}

It's still O(1) space, but it makes redundant checks and may be more complex than O(n)

score 0 · Answer 7 · answered Jun 10 '16 at 00:41

It's a bit faster to "rotate" the cycles rather than use swaps. C example:

    // reorder A in place according to sorted indices in I
    // tA is temp value for A
    for(i = 0; i < n; i++){
        if(i != I[i]){
            tA = A[i];
            k = i;
            while(i != (j = I[k])){
                A[k] = A[j];
                I[k] = k;
                k = j;
            }
            A[k] = tA;
            I[k] = k;
        }
    }

How to sort an array in-place given an array of target indices?

7 Answers7

Linked