Misha Moroshko - 2 years ago 93
Javascript Question

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

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.

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.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download