Quickest and most efficient method to search top 3 numbers?

Question

I currently have an array of around 8 - 10 numbers that changes on a periodic basis.

So around every 5 - 10 seconds the numbers get updated.

I need to get the top 3 numbers in the array every 10 seconds.

This is all done on a mobile device.

The array is the RSSI of the currently scanned access points, so in my office its usually around 10 but out in field testing it could increase to around 50.

At the minute I iterate through the array 3 times and each time I take out the three highest numbers and place them in three previously declared variables.

My question is what should I look to do to increase speed and efficiency in this instance?

Answer 1

The numbers are only 10 - do nothing. It is already efficient enough.

If the size increases, you can use a max-heap to store your numbers.

Answer 2

Why not use the Arrays.sort method which uses as far as I am aware quick sort under the hood.

Paul

EDIT: verified it uses a tuned quick sort

Answer 3

You current algorithm needs 3*n comparisons. You could perform a variation of insertion sort to improve that:

1. Put the first 3 items of the input array in the output array, sort them
2. Iterate through the rest of the items of the input array,
   1. Put each item into the output array at the right position
   2. Trim the output array to 3 items

This needs 2*n comparisons. (I'm not sure if it's worth the extra complexity, though.)