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 , hints are appreciated
Ty
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 , hints are appreciated
Ty
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.
partial_sort_copy sounds like what you need.
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 ?
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.
If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
If at first you don't succeed, try writing your phone number on the exam paper.
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?
Last edited by manzoor; 12-27-2008 at 09:50 AM.
I think Salem means that you can sort pointers to the element instead, based on the value of the elements.Originally Posted by manzoor
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.
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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.Originally Posted by manzoor
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
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.
My homepage
Advice: Take only as directed - If symptoms persist, please see your debugger
Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"
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.Originally Posted by iMalc
Look up a C++ Reference and learn How To Ask Questions The Smart WayOriginally Posted by Bjarne Stroustrup (2000-10-14)
is this ok?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; }
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?
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).
I might be wrong.
Quoted more than 1000 times (I hope).Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
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 .