0

I have a very simple question. Say I have an array

a = [10,40,30,20,60,50]

After sorting, it would be (assuming I use sort_a = a.sort())

sort_a = [60,50,40,30,20,10]

I want to create an array of indices from a which specify which location in the sorted array that element WILL BE after sorting. From the above example, the result would be

a_sortedindices = [6, 3, 4, 5, 1, 2]

..meaning 10 is in the 6th position when sorted, 40 is in the 3rd position... etc

woodhead92
  • 127
  • 1
  • 14
  • 2
    This sounds like an interview question... – DanielC May 01 '17 at 20:18
  • Can't see a much better way of doing what you want. My question is *why* do you want to do this. I suspect there is a better way to accomplish the larger goal – Brennan May 01 '17 at 20:19
  • So, `a` and `sort_a` are the inputs and `a_sortedindices` is the desired output? – Felix Kling May 01 '17 at 20:20
  • @Brennan If I have a list of scores I am assigning ranks to and can iterate through the list only in the same order and not the sorted order. – woodhead92 May 01 '17 at 20:21
  • @FelixKling a is the only input. a_sort would just be a.sort(). And yes, the solution would be a_sortedindices – woodhead92 May 01 '17 at 20:22
  • @DanielC Haha right. – woodhead92 May 01 '17 at 20:22
  • It sounds to me like you should be using a more comprehensive data structure to make your ranks match up with the scores. An object that maps scores to ranks, for example. That way, you don't have to keep track of matching ordering from one array to another like this – Brennan May 01 '17 at 20:22
  • @Brennan The code I am working with has already evolved to a point where the datatypes are established and I cant introduce new values. All I get is a list and need to return the sortedindexlist. – woodhead92 May 01 '17 at 20:24
  • 1
    Possible duplicate of [Javascript: Sort array and return an array of indicies that indicates the position of the sorted elements with respect to the original elements](http://stackoverflow.com/questions/3730510/javascript-sort-array-and-return-an-array-of-indicies-that-indicates-the-positi) – Ricky Ruiz May 01 '17 at 20:24
  • @Ricky I checked that solution. It gives the opposite. A 'was' relationship more that a 'will be' relationship. – woodhead92 May 01 '17 at 20:25

5 Answers5

2
  1. Pair the values with their current indices
  2. Sort the array of pairs based on the original values
  3. Combine the pairs with their new indices
  4. Sort the new array based on the original indices
  5. Obtain the new indices from the sorted array

let values = [10,40,30,20,60,50];

let indices = values
    .map((v, i) => ({ v, i }))
    .sort((l, r) => r.v - l.v)
    .map(({v, i}, i2) => ({ v, i, i2 }))
    .sort((l, r) => l.i - r.i)
    .map(p => p.i2);

console.log(indices);

This results in an array of 0-based indices because JavaScript uses 0-based indices. If you want 1-based indices like in your question, you can change p.i2 to p.i2 + 1 in the second to last line.

JLRishe
  • 99,490
  • 19
  • 131
  • 169
  • This is like detonating opened door. Used five loops, while one map and sort is fairly enough. – kind user May 01 '17 at 20:39
  • @Kinduser Then by all means, please add your own answer and show us how to do it with one map and sort. – JLRishe May 01 '17 at 20:40
  • To be honest I was almost to add a very similar answer to Joseph's, but I was just hesitating, because it seemed too trivial for me. I don't know what to think about this question. – kind user May 01 '17 at 20:42
  • @Kinduser If my answer is like detonating an open door, then Joseph's is like flinging coins in a lake to dive in and find them again. It also doesn't work if the original array contains duplicates. – JLRishe May 01 '17 at 20:47
2

One of the ways, apart from many to achieve this:
1) Transform the array into another with old indices

2) Sort the array in descending order

3) Create an answer array since you now know the old and new indices.

let a = [10,40,30,20,60,50];
let transformed = a.map((v,i)=> {
    return {num:v,old:i};
});
transformed.sort((a,b)=> {
 return b.num - a.num;
});
let ans = [];
transformed.forEach((v,i) => {
 ans[v.old] = i+1;
});

console.log(ans);
Pankaj Shukla
  • 2,657
  • 2
  • 11
  • 18
  • @JLRishe Thanks! Removed return from forEach, was a typo. Set the i too. Thanks for i part too! Well. i+1 is required as OP is asking for 1 based index. – Pankaj Shukla May 01 '17 at 20:54
  • Yeah, the last `i + 1` is needed in order to match OP's requested output. And I deleted my first comment, so I'll say again here: Nice answer. :) – JLRishe May 01 '17 at 21:04
1

Not sure if this is a trick question or if you're trying to find the most minimal method for achieving this, but you basically already have it. This is what I came up with:

var a = [10,40,30,20,60,50];
var sort_a = a.slice(0).sort((a1,a2) => a2 - a1);
var a_sortedindices = a.map( a1 => sort_a.indexOf(a1) + 1 );
console.log(a_sortedindices);

Walking through it, I'll explain each part.

First, off you have to sort it. Looks like you need reverse sorting, so we'll add an arrow function describing a reverse sort, but before we do that, we'll also clone the array, otherwise we'll lose the original indexes of the values. .slice(0) is a nice way to return a clone of an array

var sort_a = a.slice(0).sort((a1,a2) => a2 - a1);

Then we'll map each value of the origin array. .map() is nice and easy to quickly manipulate each element in an array. We use .indexOf() to figure out where it was at in the original array. We add one to that value because you're not using zero-based indexing.

var a_sortedindices = a.map( a1 => sort_a.indexOf(a1) + 1 );

And voila. You have the sorted indexes.

Joseph Marikle
  • 76,418
  • 17
  • 112
  • 129
  • "minimal" in what sense? `a.map( a1 => sort_a.indexOf(a1) + 1 );` is an O(n^2) operation. – JLRishe May 01 '17 at 20:38
  • @JLRishe I didn't state that clearly enough. My attempt it not minimal or an attempt at fast execution time. It's straightforward and similar to how OP described the steps of the operation. What I don't know is why OP didn't write it out himself. Is he looking for a minimal approach, a fast approach? If so, my answer is not that useful, so I don't know. It would have helped if OP included his attempts. – Joseph Marikle May 01 '17 at 20:42
  • I agree. It would have been nice if OP had shown some of their own effort in coding a solution. – JLRishe May 01 '17 at 20:44
1

A naive way of doing this job could be;

var arr = [10,40,30,20,60,50],
    idx = arr.map(function(n){return this.indexOf(n)+1;}, arr.slice().sort((a,b) => b-a));
console.log(idx);

where the this argument for the .map() function callback is arr.slice().sort((a,b) => b-a)

Redu
  • 25,060
  • 6
  • 56
  • 76
0
// the array to be sorted
var list = [10,20,30,40];

// temporary array holds objects with position and sort-value
var mapped = list.map(function(el, i) {
  return { index: i, value: el };
})

// sorting the mapped array
mapped.sort(function(a, b) {
  return b.value - a.value;
});

// you can then remap the sorted mapped array to hold just the indices

P.S.: For future reference MDN is your friend

Sebastian L. Hellsing
  • 21
  • 1