c++: Best sorting algorithm for sorting only the top 5 maximum values

Question

vector<int> arr = [3, 89, 97, 8, 67, 6, 3, 2, 56, 78, 1, 45, 63, 4, 53]

I intend to extract [ 53, 63, 78, 89, 97] - top 5 elements in the order from lowest to highest

Please help me with following:

First, in terms of algorithmic complexity, would below code cost more?

sort(arr.begin(), arr.end(), greater<char>());
for (int j = 9; j>=0;j--){
    cout << "Array elements: " << arr[j] << endl;
}

Second, do we have any descending order arrangement feasibility in partial_sort(). If yes, will it cost less in comparison to #1?

What do you mean by "would below code cost more"? Compared to what? — Cheers and hth. - Alf, Sep 04 '16 at 11:05
Complexity and cost are very different things. Please don't confuse both. — Rohith R, Sep 04 '16 at 11:07
Cost refers to performance and comparison would be with respect to first and second approach — user6792945, Sep 04 '16 at 11:10
None of the two approaches mentioned are particularly efficient compared to the natural straightforward approach, that of just scanning the array and keeping the five highest values, which is linear complexity. — Cheers and hth. - Alf, Sep 04 '16 at 11:20
Your vector `arr` contains `int`s, yet you use `greater()` if that's intentional, then *why*? I'd say you should be using `greater()`. — Jesper Juhl, Sep 04 '16 at 12:03

score 3 · Answer 1 · answered Sep 04 '16 at 11:22

You are looking for the std::partial_sort function:

partial_sort(arr.begin(), arr.begin() + 5, arr.end(), greater<char>());

This gives you the greatest five elements in the start, and won't bother sorting the rest.

The running time is O(N log K) where N is the size of the array and K is the number of elements you are interested in, so it is going to be O(N) given K = 5 is fixed.

score 2 · Answer 2 · edited May 23 '17 at 10:34

Here are some ideas that you can explore on. I am not giving away the solution yet.

Solution for a more general problem :

Search for Kth order statistic. Expected average case runtime is O(n). Then its just a matter of another loop to partition the elements greater than that statistic and less than the statistic. Something like the partitioning algorithm of Quicksort.

So overall complexity is still O(n).

Now your question talks about cost finding 5 best elements :

This has nothing to do with complexity. There are varied approaches one can follow :

What if you wanted the top 2 elements :

One of the most effective approaches will be to maintain 2 variables largest and second_largest and update them with a single run of a loop.

int a[] = {1,2,3,4,5,6,6,78,567,5675673,345242,234,231,12,12,50};
int largest = -1,second_largest = -1; // Let's assume numbers are positive. It doesn't matter.
for (int i=0;i<N;i++)
    if (a[i] > largest)
    {
        second_largest = largest;
        largest = a[i];
    }
    else if (a[i] > second_largest)
        second_largest = a[i];

Now as you want top - 5 elements you can still do the same. Maybe this might prove to be the best in terms of cycle-accurate run-time.

Another approach is to maintain a Heap Data Structure. There are some interesting ways to solve your problem using heaps. (Again I am not giving away much)

Last comments : This kind of approach is used in mobile phone contact directories, where as soon as you open they have to show you some top - X contacts in some order. So there are a bunch of research papers also on this.

Very interesting how a simple problem can lead to some complicated solutions when applied to real life !

I hope you enjoyed reading and explore on your own to find what's the best for you.

c++: Best sorting algorithm for sorting only the top 5 maximum values

2 Answers2