CODEWITHSUNDEEP
c#.netalgorithmsorting
evanmcdonnal
evanmcdonnal

Reputation: 48096

Most efficient way to sort for x/n elements in an array - .NET

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?

Upvotes: 0

Views: 268

Answers (2)

Kakira
Kakira

Reputation: 856

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.

Upvotes: 0

Samy Arous
Samy Arous

Reputation: 6814

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.

Upvotes: 1

Related Questions