Algorithm which returns 3 largest values in array sorted JS

Question

I am attempting to write a solution to a pretty common alg. Input is a non sorted array and the output should be an array of the three highest valuest sorted.

My approach is to default set the first three items of the array to be the three largest. Loop through every element in the array starting from idx 3 and run each value through a series of functions that compares that value to each of the present 3 highest.

MY CODE

function findThreeLargestNumbers(array) {

  let currentHighest = array[0];
  let secondHighest = array[1];
  let thirdHighest = array[2]
  
  for(i = 3; i < array.length; i++){
    compareFirst(array[i], currentHighest, secondHighest, thirdHighest);
  }
  console.log(currentHighest, secondHighest, thirdHighest)
}


function compareFirst(value, currentHighest, secondHighest, thirdHighest){
  if(value >= currentHighest){

    let pastFirst = currentHighest;
    currentHighest = value;

    compareSecond(pastFirst, secondHighest, thirdHighest)
  }else{
    compareSecond(value, secondHighest, thirdHighest)
  }
}

function compareSecond(value, secondHighest, thirdHighest){
  if(value >= secondHighest){
    
    let pastSecond = secondHighest;
    secondHighest = value;
    
    compareThird(pastSecond, thirdHighest);
  }else{
    compareThird(value, thirdHighest)
  }
}

function compareThird(value, thirdHighest){
  if(value >= thirdHighest){
    thirdHighest = value;
  }
}

after this is all finished in the console.log I see nothing has changed from the variables I have set above. Meaning the functions are not updating the values set in the parent function.

My approach might be way off but I'm confused as to why the values wont update globally.

Your values aren't updating because your local variables share the same name as your global variables. You're changing the local currentHighest (the parameter), not the global currentHighest (the argument). — D M
– D M, Commented Jun 8, 2022 at 18:25
@DM but passing them through params and re-setting their values should update them globally should it not? — Ben_Sven_Ten
– Ben_Sven_Ten, Commented Jun 8, 2022 at 18:27
Possibly; if they were objects. Primitives behave as if they were passed-by-value. — D M
– D M, Commented Jun 8, 2022 at 18:34

Anthony Lapin · Accepted Answer · 2022-06-08 18:55:41Z

JavaScript has data types passed by value - Primitive types (number, boolean, string and etc.) and data types passed by reference - Objects (Array, Function, Object).

When you pass primitive type as an argument of the function, you are simply passing the value of the variable. Therefore, when you change the argument of the function passed as a primitive type, this change does not affect the variable passed outside of the function.

When you pass reference data type as an argument of the function, you are passing the address of this variable to the function, not the value itself. That's why if you change the argument passed by reference, then it will be changed as well outside of the function.

In your case, since your are passing the numbers as arguments of the compareFirst, compareSecond and compareThird functions, their values won't be changed.

Ben_Sven_Ten · Accepted Answer · 2022-06-08 19:01:06Z

As stated by others, the problem was passing Primitive Types as function params, results in having their values changed in only the local function scope but not in the global scope. Using a Reference Data Type, in this case: highestValues Object to store the values allows me to update them globally as needed from within the child functions.

SOLUTION

function findThreeLargestNumbers(array) {
  let highestValues = {}
  
  for(i = 0; i < array.length; i++){
    compareFirst(array[i], highestValues);
  }
  return [highestValues['3'], highestValues['2'], highestValues['1']];
}


function compareFirst(value, highestValues){
  if(!highestValues['1']){
    highestValues['1'] = value;
    
  }else if(value >= highestValues['1']){

    let pastFirst = highestValues['1'];
    highestValues['1'] = value;

    compareSecond(pastFirst, highestValues)
  }else{
    compareSecond(value, highestValues)
  }
}

function compareSecond(value, highestValues){
  if(!highestValues['2']){
    highestValues['2'] = value;
    
  }else if(value >= highestValues['2']){

    let pastSecond = highestValues['2'];
    highestValues['2'] = value;
    
    compareThird(pastSecond, highestValues);
  }else{
    compareThird(value, highestValues)
  }
}

function compareThird(value, highestValues){
  if(!highestValues['3']){
    highestValues['3'] = value;
    
  }else if(value >= highestValues['3']){
    highestValues['3'] = value;
  }
}

Scott Sauyet · Accepted Answer · 2022-06-08 19:41:19Z

Others have already explained what's wrong with your code.

If you're looking for a simpler approach, we can fold the numbers into our target array one step at a time, using Array.prototype.reduce, starting with an array of three copies of -Infinity.

At each step we test whether the new number is greater than the highest one, greater than the second-highest one, greater than the third-highest one, or none of the above, and return a three-element array with the new number inserted in the right place. It might look like this:

const topThree = (ns) => ns.reduce ((m, n) => 
  n > m[2] ? [m[1], m[2], n] : n > m[1] ? [m[1], n, m[2]] : n > m[0] ? [n, m[1], m[2]] : m,
  [-Infinity, -Infinity, -Infinity]
)

console.log(topThree([8, 6, 7, 5, 3, 0, 9]))

aropan · Accepted Answer · 2022-06-08 21:24:52Z

0

If you want to write less code you can think about a similar insertion sort:

function findKLargestNumbers(arr, k = 3) {
  // get first three element and sort them
  let ret = arr.slice(0, k)
  ret.sort()

  // iterate other elements
  for (i = k; i < arr.length; ++i) {
    let x = arr[i];
    for (j = 0; j < k; ++j) {
      // if current value greater then swap (imporant: without break)
      if (x > ret[j]) {
        [x, ret[j]] = [ret[j], x]
      }
    }
  }
  return ret
}

answered Jun 8, 2022 at 21:24

aropan

6361 gold badge4 silver badges9 bronze badges

Collectives™ on Stack Overflow

Algorithm which returns 3 largest values in array sorted JS

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related