I was doing this algorithm to find three integers WITHOUT sorting the input array and return a sorted array of the three largest integers in the input array. Duplicates are okay.
Is there a way to solve this without helper functions like how i did? Or maybe a more optimized solution?
function findThreeLargestNumbers(array) {
let result = [null, null, null];
for (let i = 0; i < array.length; i++) {
updateLargest(result, array[i])
}
return result
}
function updateLargest(result, num) {
if (!result[2] || num > result[2]) {
shiftAndUpdate(result, num, 2)
} else if (!result[1] || num > result[1]) {
shiftAndUpdate(result, num, 1)
} else if (!result[0] || num > result[0]) {
shiftAndUpdate(result, num, 0)
}
}
function shiftAndUpdate(array, num, index) {
for (let i = 0; i <= index; i++) {
if (i === index) {
array[i] = num;
} else {
array[i] = array[i + 1];
}
}
}
console.log(findThreeLargestNumbers([141, 1, 17, -7, -17, -27, 18, 541, 8, 7, 7]));
Assuming N ≥ 3,
B[0]:= A[0]
# First two, sorted
if A[1] ≥ A[0]
B[1]:= B[0]; B[0]:= A[1]
else
B[1]:= A[1]
# First three, sorted
if A[2] ≥ A[1]
B[2]:= B[1]
if A[2] ≥ A[0]
B[1]:= B[0]; B[0]:= A[2]
else
B[1]:= A[2]
else
B[2]:= A[2]
# Update the largest three, sorted
for i:= 3 to N-1
if A[i] ≥ A[1]
B[2]:= B[1]
if A[i] ≥ A[0]
B[1]:= B[0]; B[0]:= A[i]
else
B[1]:= A[i]
else
if A[i] ≥ A[2]
B[2]:= A[i]
At worse 2N-3 comparisons and 2N-1 moves.