I have an array of objects which all have a timestamp marking when they were last updated. I want to get a subset of the array which has only the most recently updated items. I will be retrieving only 5 elements out of an array of 50 to 100 and performance is my top priority so I am apposed to sorting the entire array with one of the classes methods. What's the best way of doing this?
Asked
Active
Viewed 261 times
0
-
1Is the array of fixed size? or is there a stream of objects being pushed on top? Why are you opposed to sorting the array? – Samy Arous Jun 02 '12 at 04:28
-
The array will be fixed in size by the time it's being sorted, but I don't know how large it will be before hand. I'm opposed to sorting the whole thing, not sorting it. I just want it to sort five elements to the top then break. There's no need to sort the rest of the elements because they won't be getting used and the array won't persist so I will see no future performance gains. – evanmcdonnal Jun 02 '12 at 04:32
2 Answers
1
I would use a insertion sort and break out once you've selected the required number of elements. This solution have an O(k*n) complexity where k is the number of elements to be extracted.
There are also algorithm that find the Kth largest element in an unsorted array in O(n)
How to find the kth largest element in an unsorted array of length n in O(n)?
Once you have found the Kth largest element X, you can traverse the array and pick all the elements that are greater than X. You are guaranteed to have exactly k-1 element superior to X.
Community
- 1
- 1
Samy Arous
- 6,794
- 13
- 20
-
This looks pretty good. I'll accept if no one posts a better answer in the next few hours. – evanmcdonnal Jun 02 '12 at 05:12
0
If you have only a 100 elements, then i'd simply sort them. Otherwise, I'd use a heap-based priority queue implementation. O(n) to create, every insert/delete from then on has a O(logn) cost associated with it.
Kakira
- 846
- 1
- 8
- 14