Ranking array elements

Question

I need an algorithm to rank elements of an array in Javascript.

Example : I have an array as follows:

[79, 5, 18, 5, 32, 1, 16, 1, 82, 13]

I need to rank the entries by value. So 82 should receive rank 1, 79 rank 2 etc. If two entries have the same value they receive the same rank and the rank for a lower value is raised.

So for this array, the new ranking array would be:

[2, 7, 4, 7, 3, 9, 5, 9, 1, 6] 

How can I do this?

Solution 1

var arr = [79, 5, 18, 5, 32, 1, 16, 1, 82, 13];
var sorted = arr.slice().sort(function(a,b){return b-a})
var ranks = arr.map(function(v){ return sorted.indexOf(v)+1 });
console.log(ranks);

Result :

[2, 7, 4, 7, 3, 9, 5, 9, 1, 6]

If you want to be compatible with old browsers, you may have to define a shim for indexOf and for map (note that if you want to do this very fast for very big arrays, you'd better use for loops and use an object as map instead of indexOf).

Solution 2

This won't work with older browsers because it uses ECMAScript 5 features, but it allows you to quickly and succinctly produce an array of rankings even for very large arrays. (It doesn't use indexOf which does a linear search and thus can be slow for large arrays.)

function cmp_rnum(a,b) {
    // comparison function: reverse numeric order
    return b-a;
}
function index_map(acc, item, index) {
    // reduction function to produce a map of array items to their index
    acc[item] = index;
    return acc;
}
function ranks(v) {
    var rankindex = v.slice().sort(cmp_rnum).reduceLeft(index_map, Object.create(null));
    // reduceLeft() is used so the lowest rank wins if there are duplicates
    // use reduce() if you want the highest rank
    return v.map(function(item){ return rankindex[item]+1; });
}

Example output:

> ranks([79, 5, 18, 5, 32, 1, 16, 1, 82, 13]);
  [2, 7, 4, 7, 3, 9, 5, 9, 1, 6]

Solution 3

function rank(arr, f) {
    return arr
    .map((x, i) => [x, i])
    .sort((a, b) => f(a[0], b[0]))
    .reduce((a, x, i, s) => (a[x[1]] =
        i > 0 && f(s[i - 1][0], x[0]) === 0 ? a[s[i - 1][1]] : i + 1, a), []);
}

Usage:

rank([79, 5, 18, 5, 32, 1, 16, 1, 82, 13], (a, b) => b - a);
// [2, 7, 4, 7, 3, 9, 5, 9, 1, 6] 

Looks a bit ugly, but it doesn't use indexOf() or an object/map, so not only does it run a little faster, but more importantly, it respects the meaning of "same rankedness" as defined by the comparison function. If one uses indexOf() or an object, "same rankedness" can only mean a === b or String(a) === String(b).

Alternatively, use findIndex():

function rank(arr, f) {
    const sorted = arr.slice().sort(f)
    return arr.map(x => sorted.findIndex(s => f(x, s) === 0) + 1)
}

Solution 4

JavaScript ES6 simple two lines solution.

var arrayRankTransform = arr => {
  const sorted = [...arr].sort((a, b) => b - a);
  return arr.map((x) => sorted.indexOf(x) + 1);
};

console.log(arrayRankTransform([79, 5, 18, 5, 32, 1, 16, 1, 82, 13]));

Solution 5

I am not good at Javascript but in PHP it can be done quite easily the following way. Somebody good at JavaScript can come up with the relevant code.

$marks = [79, 5, 18, 5, 32, 1, 16, 1, 82, 13];

public function getRank($marks) {
    $rank = 1; $count = 0; $ranks = [];
    //sort the marks in the descending order
    arsort($marks,1);
    foreach($marks as $mark) {
      //check if this mark is already ranked
      if(array_key_exists($mark, $ranks)) {
       //increase the count to keep how many times each value is repeated
       $count++;
       //no need to give rank - as it is already given
      } else {
        $ranks[$mark] = $i+$j;
        $i++;
      }
    return $ranks;
}

View more solutions

Comments

[Matt Cain]

Will the numbers in the array always be unique? Edit: Obviously not, according to the example.

[pp19dd]

This pattern doesn't make sense. Can you provide a better description of the problem?

[Ben McCormick]

they're obviously not unique in the question, 2 5s and 2 1s

[Syjin]

Have you tried it yourself before posting the question?

[Admin]

looks like homework to me....

[Chris Nadovich]

It's critical that ranking handle duplicate entries, otherwise it's just a sort. And if this is homework @CrisimIlNumenoreano it's pretty trivial homework.

[VisioN]

Looks like you guys don't read the question. It seems the OP requires to get a ranking array.

[Christoph]

the oh so old problem of the wrong sort^^ .sort(function(a,b){return a-b})

[Denys Séguret]

@Christoph Oh... you saw it before me. I spent a few minutes trying to check what was really OP question...

[Christoph]

map might need to be shimmed too (IE-9). But really nice solution!

[Francis Avila]

Instead of indexOf, you can use reduce to build a mapping. See my answer.

[timhc22]

I had to use reduceRight

[Sukhpreet Singh Alang]

rankNumbers([2, 5, 5, 10, 8], (a, b) => a - b) returns [ 1, 2, 2, 5, 4 ], i.e. skips the rank 3. I get that duplicate numbers are given the same rank, but does it make sense that rank 3 is skipped? Perhaps it does; curious about your judgement

[Sukhpreet Singh Alang]

Wouldn't you argue that both should have rank (2 + 3) / 2 = 2.5 since they share rank 2 and rank 3?

[Chris Nadovich]

Does this really work correctly with multiple duplicate entries?

[Chris Nadovich]

Is that really the correct result? There are 8 unique values. How can something be ranked 9th? Nothing is ranked 8th. I don't think this solution is valid but I don't have the rep to vote it down.

[Chris Nadovich]

I agree with you @Tom. The above algorithms don't seem to be correct. They skip rank values.

[Chris Nadovich]

I don't know why this one was voted down. It has some issues, but seems like the only one adaptable to be a correct solution. Just get rid of +$j and $count. $i increments only for unique values.

[Francis Avila]

@ChrisNadovich Result is identical to both the OP’s desired result and the result from the accepted answer. OP said: “If two entries have the same value they receive the same rank and the rank for a lower value is raised.” The 8 was was promoted to 9.

[Chris Nadovich]

OK, @FrancisAvila, I stand corrected. I guess I was blinded by my own requirement, which was for ranking of only the unique values when there are ties.

[Abdullah Aman]

Not working for array that contains duplicate values. It skips the rank.

[BurnsBA]

uncaught TypeError: reduceLeft is not a function. It looks like this should be reduce