Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 521
Jeremy Avatar asked Sep 16 '10 20:09

Jeremy


People also ask

What does array sort return in JavaScript?

The sort() method sorts the elements of an array in place and returns the reference to the same array, now sorted. The default sort order is ascending, built upon converting the elements into strings, then comparing their sequences of UTF-16 code units values.

How do you sort an index array?

sort(long[], int, int) method sorts the specified range of the specified array of longs into ascending numerical order. The range to be sorted extends from index fromIndex, inclusive, to index toIndex, exclusive.

Can you sort an array in JavaScript?

JavaScript Array sort()The sort() sorts the elements of an array. The sort() overwrites the original array. The sort() sorts the elements as strings in alphabetical and ascending order.


3 Answers

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(",")); 
like image 71
Dave Aaron Smith Avatar answered Sep 19 '22 17:09

Dave Aaron Smith


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);
like image 21
Sly1024 Avatar answered Sep 18 '22 17:09

Sly1024


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)
like image 33
Matt Way Avatar answered Sep 16 '22 17:09

Matt Way