Optimized javascript code to find the 3 largest elements and its indices in an array?

Question

I need more optimized javascript code to find the 3 largest elements in an array. I tried with this code.

var maxIndex = new Array(); var maxPoints = new Array(); var scoreByPattern = new Array(93,17,56,91,98,33,9,38,55,78,29,81,60); function findLargest3(){ maxPoints[0]=0; maxPoints[1]=0; maxPoints[2]=0; for(i=0;i < scoreByPattern.length; i++){ if( scoreByPattern[i] > maxPoints[0]){ maxPoints[0] = scoreByPattern[i]; maxIndex[0]=i; } } for(i=0;i < scoreByPattern.length; i++){ if( scoreByPattern[i] > maxPoints[1] && scoreByPattern[i]< maxPoints[0] ){ maxPoints[1] = scoreByPattern[i]; maxIndex[1]=i; } } for(i=0;i < scoreByPattern.length; i++){ if( scoreByPattern[i] > maxPoints[2] && scoreByPattern[i]< maxPoints[1] ){ maxPoints[2] = scoreByPattern[i]; maxIndex[2]=i; } } alert(scoreByPattern+"/******/"+maxPoints[0]+"/"+maxPoints[1]+"/"+maxPoints[2]); //alert(maxIndex); } 

How to optimize the above? (I need indices of the largest numbers) Are there any other easy methods to solve the problem?

Answer 1

Disconnect sorting in descending order, then get the first three elements:

 var maxPoints = new Array(); var scoreByPattern = new Array(93,17,56,91,98,33,9,38,55,78,29,81,60); findLargest3(); function findLargest3(){ // sort descending scoreByPattern.sort(function(a,b) { if (a < b) { return 1; } else if (a == b) { return 0; } else { return -1; } }); alert(scoreByPattern+"/******/"+scoreByPattern[0]+"/"+scoreByPattern[1]+"/"+scoreByPattern[2]); } 

Script example

Answer 2

Modified version

I modified my answer to make it more general. It searches the indices n of the largest number of elements in the array:

 var scoreByPattern = [93,255,17,56,91,98,33,9,38,55,78,29,81,60]; function findIndicesOfMax(inp, count) { var outp = []; for (var i = 0; i < inp.length; i++) { outp.push(i); // add index to output array if (outp.length > count) { outp.sort(function(a, b) { return inp[b] - inp[a]; }); // descending sort the output array outp.pop(); // remove the last index (index of smallest element in output array) } } return outp; } // show original array console.log(scoreByPattern); // get indices of 3 greatest elements var indices = findIndicesOfMax(scoreByPattern, 3); console.log(indices); // show 3 greatest scores for (var i = 0; i < indices.length; i++) console.log(scoreByPattern[indices[i]]); 

Here is jsFiddle

Answer 3

Without sorting a huge array: performed in O(n) given the large array. Returns an array of an array with [x,y] , where x is the value and y index in the large array.

 var ar = [3,172,56,91,98,33,9,38,55,78,291,81,60]; function getMax(ar){ if (ar.length < 3) return ar; var max = [[ar[0],0],[ar[1],1],[ar[2],2]], i,j; for (i = 3;i<ar.length;i++){ for (j = 0;j<max.length;j++){ if (ar[i] > max[j][0]){ max[j] = [ar[i],i]; if (j<2){ max.sort(function(a,b) { return a[0]-b[0]; }); } break; } } } return max; } result = getMax(ar); console.log(result); alert(result); 

check example

Answer 4

The default sorting callback javascript will not work because it sorts into a lexicographic order . 10 will be up to 5 (because of 1)

No credit for me, but:

 my_array.sort(function(a,b) { return ab; }); 

Answer 5

Assuming a fairly normal distribution, this should be reasonably optimal:

 var max_three, numbers = new Array(93,17,56,91,98,33,9,38,55,78,29,81,60); max_three = (function (numbers) { var i, one, two, three; one = -9999; two = -9999; three = -9999; for (i = 0; i < numbers.length; i += 1) { num = numbers[i]; if (num > three) { if (num >= two) { three = two; if (num >= one) { two = one; one = num; } else { two = num; } } else { three = num; } } } return [one, two, three] }(numbers)) document.write(max_three)​​​​​​​ 

98.93.91

Answer 6

Why don't you just sort it and move the first (or last, if sorted ascending) three elements.

 var maxPoints = new Array(); var scoreByPattern = new Array(93,17,56,91,98,33,9,38,55,78,29,81,60); scoreByPattern.sort(); maxPoints[0] = scoreByPattern[scoreByPattern.length - 1]; maxPoints[1] = scoreByPattern[scoreByPattern.length - 2]; maxPoints[2] = scoreByPattern[scoreByPattern.length - 3]; 

Edit
If you need the indices of the largest arrays, you can create a copy that you sort, and then find the indices in the original array:

 var scoreByPattern = new Array(93,17,56,91,98,33,9,38,55,78,29,81,60); // Make a copy of the original array. var maxPoints = scoreByPattern.slice(); // Sort in descending order. maxPoints.sort(function(a, b) { if (a < b) { return 1; } else if (a == b) { return 0; } else { return -1; } }); // Find the indices of the three largest elements in the original array. var maxPointsIndices = new Array(); maxPointsIndices[0] = scoreByPattern.indexOf(maxPoints[0]); maxPointsIndices[1] = scoreByPattern.indexOf(maxPoints[1]); maxPointsIndices[2] = scoreByPattern.indexOf(maxPoints[2]); 

Another approach for finding indexes without sorting is as follows:

 var scoreByPattern = new Array(93,17,56,91,98,33,9,38,55,78,29,81,60); var maxIndices = new Array(Number.MIN_VALUE, Number.MIN_VALUE, Number.MIN_VALUE); for (var i = 0; i < scoreByPattern.length; i++) { if (maxIndices[0] < scoreByPattern[i]) { maxIndices[2] = maxIndices[1]; maxIndices[1] = maxIndices[0]; maxIndices[0] = scoreByPattern[i]; } else if (maxIndices[1] < scoreByPattern[i]) { maxIndices[2] = maxIndices[1]; maxIndices[1] = scoreByPattern[i]; } else if (maxIndices[2] < scoreByPattern[i]) maxIndices[2] = scoreByPattern[i]; } 

Answer 7

The best way is to use a combination of sort and slice :

This simple liner will solve your problem.

 [1, -5, 2, 8, 17, 0, -2].sort(function(a, b){return b - a}).slice(0, 3) 

So, if you have an array and want to find the N largest values:

 arr.sort(function(a, b){return b - a}).slice(0, n) 

And for the N smallest values:

 arr.sort(function(a, b){return a - b}).slice(0, n) 

Answer 8

http://jsfiddle.net/GGkSt/

 var maxPoints = []; var scoreByPattern = [93,17,56,91,98,33,9,38,55,78,29,81,60]; function cloneArray(array) { return array.map(function(i){ return i; }); } function max3(array) { return cloneArray(array).sort(function(a,b) { return ba; }).slice(0,3); } function min3(array) { return cloneArray(array).sort(function(a,b) { return ab; }).slice(0,3); } var array=scoreByPattern; alert("Max:"+ max3(array)[0] +' '+max3(array)[1] +' '+max3(array)[2]); alert("Min:"+ min3(array)[0] +' '+min3(array)[1] +' '+min3(array)[2]);