# find top n elements

• 11-16-2008
manzoor
find top n elements
How to find the top n elements without sorting the array?

Is this possible???

Well I don't want to sort the array because the order is mandatory?

I don't want a direct solution to this, and this is no homework :D, hints are appreciated

Ty
• 11-16-2008
tabstop
Within the last week, someone asked how to find the five smallest elements. Changing "smallest" to "largest" and "5" to "n" would give the same answer, I should think.
• 11-16-2008
Daved
partial_sort_copy sounds like what you need.
• 12-27-2008
manzoor
What do u mean?
I want the top n elements in the array without sorting the original array, and then want to make modifications to the top n elements without changing the order of the array

How ?
• 12-27-2008
Salem
An array of n pointers to the top-n elements of the array.

This is of course always sorted, so you only compare a[i] with pa[n-1] to determine if you've got a new top-n entry.
• 12-27-2008
manzoor
Can u simplify what you mean?

Do you mean that I create n pointers to the top elements?

Ok but if I go this way, I'm still having an obstacle on my way. How should I determine the top n elements? Should I sort a copy of the array? or If I find the top element using max_element, then how do I find the next top element?
• 12-27-2008
laserlight
Quote:

Originally Posted by manzoor
Can u simplify what you meaan?

I think Salem means that you can sort pointers to the element instead, based on the value of the elements.

One way would be to create a vector of pointers to the elements of the container. If you need the top n elements in sorted order, then use std::partial_sort(), otherwise use std::nth_element() on the vector of pointers with some suitable predicate so that you can sort based on the elements rather than their addresses. When you are done, just take the first n pointers from the vector.
• 12-30-2008
manzoor
Can we sort the elements with their pointers and modify them without changing their order in the original array?
• 12-30-2008
laserlight
Quote:

Originally Posted by manzoor
Can we sort the elements with their pointers and modify them without changing their order in the original array?

Yes, that's what we've been talking about.
• 12-30-2008
iMalc
Yes, just build an array of pointers where each pointer points to an item in the originaly array. Then sorting is done by comparing what the pointers in that array point to, but swapping is done directly on those pointers.
For efficiency, you should also either keep the pointer array around all the time and keep it up to date,
OR you can create it each time, but not perform a full sort, and by that I mean performing Quicksort partitioning steps, but mostly only on the upper partition, and only on the lower partition when the upper one plus the pivot doesn't give enough items. This avoids a full sort, but still gives you the items you want. partial_sort_copy probably does something like this so you don't have to code that yourself. Just use greater-than as your comparison function.
• 12-30-2008
laserlight
Quote:

Originally Posted by iMalc
OR you can create it each time, but not perform a full sort, and by that I mean performing Quicksort partitioning steps, but mostly only on the upper partition, and only on the lower partition when the upper one plus the pivot doesn't give enough items. This avoids a full sort, but still gives you the items you want. partial_sort_copy probably does something like this so you don't have to code that yourself.

It depends: as I mentioned in post #7, partial_sort is appropriate if the elements are to be in sorted order, otherwise nth_element is likely to be more appropriate.
• 01-03-2009
manzoor
Code:

```#include <iostream> #include <vector> #include <ctime> #include <algorithm> #include <numeric> bool myFunction(int* i, int* j) {         return *i > *j; } using namespace std; int main() {         vector<int> numbers;         vector<int*> pNumbers;         srand(time(0));         const int vecSize = 10;         for (size_t i = 0; i < vecSize; i++)         {                 numbers.push_back(rand() % 10 + 1);                 cout << numbers.at(i) << endl;                 pNumbers.push_back(&numbers.at(i));         }         partial_sort(pNumbers.begin(), pNumbers.begin() + 5, pNumbers.end(), myFunction);         cout << endl << endl << endl;         for (size_t i = 0; i < pNumbers.size(); i++)                 cout << *pNumbers[i] << endl;         return EXIT_SUCCESS; }```
is this ok?

But this isn't working, there's something wrong in the assigning the pointers. What am I doing wrong, am I initializing the pointers correctly?
• 01-03-2009
anon
Take the addresses only after you have finished pushing back the main data. A push_back can move everything to another place in memory if the vector runs out of space, so all the pointers in the second vector become invalid (or use indices instead of pointers / or reserve enough memory in the first vector so the data won't be relocated).
• 01-03-2009
manzoor
Thanks everyone, I think I got it now.

Again thanks everyone for helping. This site has been a great resource for programming. Keep it up. I'm waiting for the day when I'll be helping people :).
• 01-03-2009
brewbuck
Quote:

Originally Posted by Daved
partial_sort_copy sounds like what you need.

Nice. An STL algorithm I haven't heard of before. Thanks Daved.

EDIT: Probably because in this sort of circumstance, I have always used a heap.