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

Your algorithm is already O(n), quick sort is > O(n log n) so that's certainly not the way to do it. You can increase the speed to O(log n) if you use a tree structure, e.g AVL tree. As for arrays only, your current one is the fastest way to do it.

Answer 4

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.)

Answer 5

I think in the general case you should use you use the QuickSelect algorithm which is based on QuickSort and, in time O(n) modifies your array inline and 'quasi-sort' it.

Say your array is A[1..10] and not sorted, by calling QuickSelect( A, 7 ) you are asking 'Which is the number that, in the sorted array should be in the seventh position?', and that is the same as saying 'Which number is the third bigger in this particular array?'. Now the great thing is that QuickSelect ensures that after this call A[i] <= A[7] for all 0 < i < 7 and that A[7] <= A[j] for all 7 < j. More info in wikipedia Quick Selection Algorithm.

Anyways as the size is just 10, you could use insertion-sort (worst case O(n^2) but works good with small arrays) and then get the three first/last elements

EDIT: - Tree structures are an overkill for just ten elements, and in general involves a time/space tradeoff ( you need a lot of pointers ) - QuickSelect has an O(n^2) worst case scenario, but 'Median-of-Medians' achieves the same result in a worst case O(n)