How To Sort An Array In-place Given An Array Of Target Indices?

July 30, 2023 Post a Comment

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

Solution 1:

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.

Solution 2:

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

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

functionrearrange(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"];

Solution 3:

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 arrayfor(var counter = 0; counter < len; counter++)
  {
     temp[ind[counter]] = arr[counter];
  }  
  //copy the values as per new indices from tempfor(var counter = 0; counter < len; counter++)
  {
     arr[counter] = temp[counter];
  }  
}

Solution 4:

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

Solution 5:

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

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

functionrearrange(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)

javascript magazin