[removed] Sort array and return an array of indici

Question

Suppose I have a Javascript array, like so:

var test = ['b', 'c', 'd', 'a'];

I want to sort the array. Obviously, I can just do this to sort the array:

test.sort(); //Now test is ['a', 'b', 'c', 'd']

But what I really want is an array of indices that indicates the position of the sorted elements with respect to the original elements. I'm not quite sure how to phrase this, so maybe that is why I am having trouble figuring out how to do it.

If such a method was called sortIndices(), then what I would want is:

var indices = test.sortIndices();
//At this point, I want indices to be [3, 0, 1, 2].

'a' was at position 3, 'b' was at 0, 'c' was at 1 and 'd' was a 2 in the original array. Hence, [3, 0, 1, 2].

One solution would be to sort a copy of the array, and then cycle through the sorted array and find the position of each element in the original array. But, that feels clunky.

Is there an existing method that does what I want? If not, how would you go about writing a method that does this?

Answer 1

I would just fill an array with numbers 0..n-1, and sort that with a compare function.

var test = ['b', 'c', 'd', 'a'];
var len = test.length;
var indices = new Array(len);
for (var i = 0; i < len; ++i) indices[i] = i;
indices.sort(function (a, b) { return test[a] < test[b] ? -1 : test[a] > test[b] ? 1 : 0; });
console.log(indices);

Answer 2

Dave Aaron Smith is correct (I cannot comment), however I think it is interesting to use Array map() here.

var test = ['b', 'c', 'd', 'a'];
// make list with indices and values
indexedTest = test.map(function(e,i){return {ind: i, val: e}});
// sort index/value couples, based on values
indexedTest.sort(function(x, y){return x.val > y.val ? 1 : x.val == y.val ? 0 : -1});
// make list keeping only indices
indices = indexedTest.map(function(e){return e.ind});

Answer 3

You can accomplish this with a single line using es6 (generating a 0->N-1 index array and sorting it based on the input values).

var test = ['b', 'c', 'd', 'a']

var result = Array.from(Array(test.length).keys())
                  .sort((a, b) => test[a] < test[b] ? -1 : (test[b] < test[a]) | 0)

Answer 4

Array.prototype.sortIndices = function (func) {
    var i = j = this.length,
        that = this;

    while (i--) {
        this[i] = { k: i, v: this[i] };
    }

    this.sort(function (a, b) {
        return func ? func.call(that, a.v, b.v) : 
                      a.v < b.v ? -1 : a.v > b.v ? 1 : 0;
    });

    while (j--) {
        this[j] = this[j].k;
    }
}

YMMV on how you feel about adding functions to the Array prototype and mutating arrays inline, but this allows sorting of an array of any objects that can be compared. It takes an optional function that can be used for sorting, much like Array.prototype.sort.

An example,

var test = [{b:2},{b:3},{b:4},{b:1}];

test.sortIndices(function(a,b) { return a.b - b.b; });

console.log(test); // returns [3,0,1,2]

Answer 5

var test = ['b', 'c', 'd', 'a'];
var test_with_index = [];
for (var i in test) {
    test_with_index.push([test[i], i]);
}
test_with_index.sort(function(left, right) {
  return left[0] < right[0] ? -1 : 1;
});
var indexes = [];
test = [];
for (var j in test_with_index) {
    test.push(test_with_index[j][0]);
    indexes.push(test_with_index[j][1]);
}

Edit

You guys are right about for .. in. That will break if anybody munges the array prototype, which I observe annoyingly often. Here it is with that fixed, and wrapped up in a more usable function.

function sortWithIndeces(toSort) {
  for (var i = 0; i < toSort.length; i++) {
    toSort[i] = [toSort[i], i];
  }
  toSort.sort(function(left, right) {
    return left[0] < right[0] ? -1 : 1;
  });
  toSort.sortIndices = [];
  for (var j = 0; j < toSort.length; j++) {
    toSort.sortIndices.push(toSort[j][1]);
    toSort[j] = toSort[j][0];
  }
  return toSort;
}

var test = ['b', 'c', 'd', 'a'];
sortWithIndeces(test);
alert(test.sortIndices.join(","));