Javascript: Sort array and return an array of indices that indicates the position of the sorted elements with respect to the original elements

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?

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(","));

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

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)

console.log(result)

Dave Aaron Smith is correct, 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});

This is a more idiomatic ES6 version of clerbois' answer, see theirs for comments:

return test.map((val, ind) => {return {ind, val}})
           .sort((a, b) => {return a.val > b.val ? 1 : a.val == b.val ? 0 : -1 })
           .map((obj) => obj.ind);

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]

You can do this with the Map object. Just set the key/value as index/value and use the Array.from to get the Iterator as a bi-dimensional array then sort either the indexes, the values or both.

function sorting(elements) {
  const myMap = new Map();
  elements.forEach((value, index) => {
    myMap.set(index, value);
  });
  const arrayWithOrderedIndexes = Array.from(myMap.entries()).sort((left, right) => {return left[1] < right[1] ? -1 : 1});
  myMap.clear();
  return arrayWithOrderedIndexes.map(elem => elem[0]);
}
const elements = ['value','some value','a value','zikas value','another value','something value','xtra value'];
sorting(elements);

We don't need to touch the existing structure of the array, instead we can put the extra work on the side, so that we can make the functionality more modular.

Array.prototype.sortIndices = function(compare) {
  const arr = this
  const indices = new Array(arr.length).fill(0).map((_, i) => i)

  return indices.sort((a, b) => compare(arr[a], arr[b]))
}

To use it for char character,

test.sortIndices((a, b) => a.charCodeAt(0) - b.charCodeAt(0))

The syntax is similar to the sort. Of course you can swap in different sorting algorithm, as long as the interface of comp holds.

Run it here:

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

Array.prototype.sortIndices = function(comp) {
	const indices = new Array(this.length)
		.fill(0).map((_, i) => i)
	return indices.sort((a, b) => comp(this[a], this[b]))
}

const { log } = console
log(test.sortIndices((a, b) => a.charCodeAt(0) - b.charCodeAt(0)))

You can use Array.prototype.entries() to pair the items with their indices. You could also use Object.entries() but that would convert the index numbers to strings.

let test = ["b", "c", "d", "a"];

console.log(
  Array.from(test.entries())
    .sort(([_, v], [__, w]) => v.localeCompare(w))
    .map(([i, _]) => i)
);

.as-console-wrapper {top:0; max-height: 100% !important}

you can do this !

detailItems.slice()
   .map((r, ix) => {
       r._ix = ix;
       return r;
   })
   .sort((a,b) => {
      ... /* you have a._ix or b._ix here !! */
   })

.slice() clones your array to prevent side effects :))