How to implement the issuance of a random element from an array, taking into account the rating?

Question

JavaScript

Help to solve the problem, there is an array with objects on the server. Each object has, roughly speaking, a name (which does not matter now) and a rating. This rating is changed by clicking on the item's rating button, which is added and divided by the number of ratings. Task: to implement a mechanism for randomly displaying an element on the UI with a higher priority bias towards elements with a low rating, that is, not just showing the element with the lowest rating, but for elements with a low rating to have priority, preferably without introducing third-party values, such as priority

Answer 1

If I understood the problem correctly, then I would solve it like this.
1. Sort the array in descending order of the evaluation value. PS In fact, it turned out that it is not necessary.
2. Further, we proceed from such considerations. Let the sum of all estimates sum(M(i)) be equal to S and take this as a 100% probability. That is, with 00% probability one of the elements of our array will be selected.
Then the probability of the i-th element falling out will be proportional to its estimate: P(i) = M(i)/S
3. We will go through each element of the sorted array and calculate the probability P(i). We choose a random number P = random()*N, where N is the remaining number of failed elements. If P < P(i), then show this random element i and end the loop.
4. Recalculate S = sum(M(i)) for all remaining elements.
Complexity of algorithm turns out O(N^2)
It so, at once the decision.
But it can be improved to at least O(N), and possibly even O(1). But then you have to introduce an additional probability field.
UPD: I'll take an example from the comments:
Let's have an array of ratings [5, 5, 3, 2]
The sum of all ratings S = 5+5+3+2 = 15
Probabilities of choosing each element:
[5/15, 5/15, 3/15, 2/15] = [0.33333, 0.33333, 0.2, 0.133333], they add up to 1, as they should.
1. Take the first element with a score of 5 and select it with a probability of 0.3333: P = random()*1.0
If P<0.333, then select the 1st element and finish the job. Otherwise we move on
2. Take the 2nd element with a score of 5. Now our probability has changed and we recalculate it so that the total is 1:
S = 5 + 3+ 2 = 10
Recalculate the probabilities:
[5/10, 3/10, 2/ 10] = [0.5 ,0.3, 0.2] - the sum is again 1, as it should be.
Now, with a probability of 0.5, we determine whether we take the 2nd element as a result or not: P = random() * 1.0
If P< 0.5, then finish the job. Otherwise, let's move on.
3. Recalculate the total scores: S = 3 + 2 = 5
New probabilities for the remaining scores: [3/5, 2/5] = [0.6, 0.4], in total again 1
With a probability of 0.6, we determine whether we keep the 3rd element as result or not.
If not, then
4. Recalculate the sum of the remaining grades: S = 2.
New probabilities for the remaining estimates: [2/2] = [1].
That is, with 100% probability we take the last element.
But to get to the last element, you have to wade through the thorns of higher ratings. Difficult, unlikely, but in principle it is possible.
UPD: To optimize the calculation of the new sum S, we simply subtract the value of the assessment of the i-th element from the previous S. Reducing the algorithm to O(N)
UPD2: If you need to invert and make the elements with the lowest scores shown more often, then you need to invert the probability: 1-P
UPD3, solution in O(1) time I thought again and the solution turned out to be even more more simple.
Let us have an array of estimates [5, 5, 3, 2]
Sum of all estimates S = 5+5+3+2 = 15
The probabilities of choosing each element:
[5/15, 5/15, 3/15, 2/15] = [0.33333, 0.33333, 0.2, 0.133333]
We build a segment, putting these four values ​​on it.
We take a random number from 0 to 1 and see which of these four segments it falls into. Here is the solution.
If it is necessary that unlikely estimates fall out, then we build inverted probabilities:
[0.6666, 0.6666, 0.8, 0.8666666]

Answer 2

Quite a common task. You should just sort the array of objects. Usually a sorted array is already sent from the server, but it can also be done on the client.
example stolen from https://www.sitepoint.com/sort-an-array-of-objects...

const singers = [
  { name: 'Steven Tyler', band: 'Aerosmith', born: 1948 },
  { name: 'Karen Carpenter', band: 'The Carpenters', born: 1950 },
  { name: 'Kurt Cobain', band: 'Nirvana', born: 1967 },
  { name: 'Stevie Nicks', band: 'Fleetwood Mac', born: 1948 },
];

function compareValues(key, order = 'asc') {
  return function innerSort(a, b) {
    if (!a.hasOwnProperty(key) || !b.hasOwnProperty(key)) {
      // property doesn't exist on either object
      return 0;
    }

    const varA = (typeof a[key] === 'string')
      ? a[key].toUpperCase() : a[key];
    const varB = (typeof b[key] === 'string')
      ? b[key].toUpperCase() : b[key];

    let comparison = 0;
    if (varA > varB) {
      comparison = 1;
    } else if (varA < varB) {
      comparison = -1;
    }
    return (
      (order === 'desc') ? (comparison * -1) : comparison
    );
  };
}

// array is sorted by band, in ascending order by default
singers.sort(compareValues('band'));

// array is sorted by band in descending order
singers.sort(compareValues('band', 'desc'));

Answer 3

We find a cluster of elements with a low rating, sort it in ascending order, put it at the very beginning before all the others.
Example:
Before (one digit - element rating):
5861273 Now
:
1238765 (or 2138765 or 3128765, etc.)