Pseudocode finding lowest highest 10% in array

Question

I need to find lowest and highest 10% numbers in array, the deal is I need it to work very very fast!

For example for array of: 20,50,77,80,6,8,41,60,63,15,31,13,90,9,34,41,54,85,93,2,52

My initial solution was to sort the array with quick-sort:

2,6,8,9,13,15,20,31,34,41,50,52,54,60,63,77,80,85,90,93

And then I easily know my highest and lowest 10%

Low: 2,6 High: 90,93

But the thing is that this array changes very fast, and sorting solution does not work for me. Any one have suggestion how fast to find what I need?

Answer 1

I don't see another solution than sorting. However, if you have the freedom of organizing things in your own data structures and control the input array, you could do maybe this to save time:

1. create an ordered list (or other ordered structure) in the size of 10 % of your original array. Provide methods to add elements into this ordered list. The other answer suggests B trees, which might also be used for this approach.
2. when adding elements to the original array, also add the element to your ordered list
3. the ordered list will always contain the top 10 percent.

The improvement over the approach of Aston is probably very small for large data sets, since the algorithm only increases my logarithmic scale. however, if your dataset is small there might be a real benefit of using only a 10 % size ordered data structure.

NOTE: If elements get removed from the original array, my approach might be less good than just using Aston suggestion from the start on, since a removal of an element might trigger a complete run over the list to fill the orderd structure again completely.

Answer 2

I think you need to consider using a different data structure for storing your data. For example, using a B tree would mean that you can insert and delete elements in logarithmic time, and yet your data keeps being sorted, so you can get the lowest and highest 10% in the same time as in a normal array.

http://en.wikipedia.org/wiki/B-tree