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

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

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

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

Answer 2

This is a method that allows you to use a custom comparator (compareFn or compare function):

function sortWithIndices(arr, compareFn=undefined) {
  // Create a new array of value, index pairs
  const indexedArray = arr.map((value, index) => [value, index]);

  // Sort that new array using your compare function or the default one if you didn't set a value
    indexedArray.sort(compareFn ? (a, b) => compareFn(a[0], b[0]) : (a, b) => a[0] - b[0]);

  // Map the values in that sorted array into output variables
  const sortedArray = indexedArray.map(item => item[0]);
  const sortedIndices = indexedArray.map(item => item[1]);
  return { sortedArray, sortedIndices };
}

// Test the above function using the example in MATLAB's documentation
X = [3, 6, 4, 2, 1, 5]
console.log(sortWithIndices(X).sortedIndices)

Answer 3

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

const test = ['b', 'c', 'd', 'a']
const result = Array.from(test.keys())
  .sort((a, b) => test[a].localeCompare(test[b]))
  
console.log(result)

Answer 4

You could get the indices and sort by their values of the given array.

const
    array = ['b', 'c', 'd', 'a'],
    indices = [...array.keys()].sort((a, b) => array[a].localeCompare(array[b]));

console.log(...indices);

Answer 5

This was the fastest method in my benchmark:

var a=Array.from({length:10000},()=>Math.random())
var l=a.length,o=new Array(l)
for(var i=0;i<l;i++)o[i]=i;o.sort((l,r)=>a[l]<a[r]?-1:a[l]>a[r]?1:0)

It's basically the same as the method by Sly1024 except it saves the length of the array into a variable instead of checking the length at each step of the for loop. The code became slower if I compared the value of one item subtracted from another instead of using the greater than and lesser than operators, if I created the array of indexes using Array.from instead of a for loop, if I used push instead of assigning values at an index, or if I didn't initialize the array with a length.

$ cat sortindexbench.js
var a=Array.from({length:1000},()=>Math.random())
var suite=new(require('benchmark')).Suite
suite.add('fastest',function(){
  var l=a.length,o=new Array(l);for(var i=0;i<l;i++)o[i]=i;o.sort((l,r)=>a[l]<a[r]?-1:a[l]>a[r]?1:0)
}).add('length_not_saved_in_variable',function(){
  var o=new Array(a.length);for(var i=0;i<a.length;i++)o[i]=i;o.sort((l,r)=>a[l]<a[r]?-1:a[l]>a[r]?1:0)
}).add('subtract_in_comparison_function',function(){
  var l=a.length;var o=new Array(l);for(var i=0;i<l;i++)o[i]=i;o.sort((l,r)=>a[l]-a[r])
}).add('populate_array_of_indexes_with_array_from',function(){
  var r=Array.from(Array(a.length).keys()).sort((l,r)=>a[l]<a[r]?-1:a[l]>a[r]?1:0)
}).add('array_not_initialized_with_length',function(){
  var l=a.length;var o=[];for(var i=0;i<l;i++)o[i]=i;o.sort((l,r)=>a[l]<a[r]?-1:a[l]>a[r]?1:0)
}).add('push_instead_of_assign_at_index',function(){
  var l=a.length;var o=new Array(l);for(var i=0;i<l;i++)o.push(i);o.sort((l,r)=>a[l]<a[r]?-1:a[l]>a[r]?1:0)
}).add('clerbois_and_Dexygen',function(){
  var o=a.map((v,i)=>{return{i,v}}).sort((l,r)=>l.v<r.v?-1:l.v>r.v?1:0).map((x)=>x.i)
}).add('clerbois_and_Dexygen_array_of_arrays_instead_of_object',function(){
  var o=a.map((v,i)=>[i,v]).sort((l,r)=>l[1]<r[1]?-1:l[1]>r[1]?1:0).map((x)=>x[0])
}).add('yakin_rojinegro',function(){
  var m=new Map();a.forEach((v,i)=>m.set(i,v));var o=Array.from(m.entries()).sort((l,r)=>l[1]<r[1]?-1:l[1]>r[1]?1:0).map(x=>x[0]);m.clear()
}).on('cycle',function(event){console.log(String(event.target))
}).on('complete',function(){console.log('Fastest is '+this.filter('fastest').map('name'))
}).run({'async':true})
$ npm i --save benchmark
[...]
$ node sortindexbench.js
fastest x 4,728 ops/sec ±0.15% (94 runs sampled)
length_not_saved_in_variable x 4,534 ops/sec ±3.19% (92 runs sampled)
subtract_in_comparison_function x 4,587 ops/sec ±0.30% (92 runs sampled)
populate_array_of_indexes_with_array_from x 4,205 ops/sec ±0.83% (94 runs sampled)
array_not_initialized_with_length x 4,638 ops/sec ±0.60% (96 runs sampled)
push_instead_of_assign_at_index x 4,510 ops/sec ±0.46% (95 runs sampled)
clerbois_and_Dexygen x 4,250 ops/sec ±0.86% (93 runs sampled)
clerbois_and_Dexygen_array_of_arrays_instead_of_object x 4,252 ops/sec ±0.97% (93 runs sampled)
yakin_rojinegro x 3,237 ops/sec ±0.42% (93 runs sampled)
Fastest is fastest

Answer 6

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}

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

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

Answer 11

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 12

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 13

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