Thread: find top n elements

  1. #1
    Registered User
    Join Date
    Nov 2007
    Posts
    164

    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 , hints are appreciated


    Ty

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    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.

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    partial_sort_copy sounds like what you need.

  4. #4
    Registered User
    Join Date
    Nov 2007
    Posts
    164
    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 ?

  5. #5
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    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.

  6. #6
    Registered User
    Join Date
    Nov 2007
    Posts
    164
    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.

  7. #7
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  8. #8
    Registered User
    Join Date
    Nov 2007
    Posts
    164
    Can we sort the elements with their pointers and modify them without changing their order in the original array?

  9. #9
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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"

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User
    Join Date
    Nov 2007
    Posts
    164
    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?

  13. #13
    The larch
    Join Date
    May 2006
    Posts
    3,573
    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.

    Thank you, anon. You sure know how to recognize different types of trees from quite a long way away.
    Quoted more than 1000 times (I hope).

  14. #14
    Registered User
    Join Date
    Nov 2007
    Posts
    164
    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 .

  15. #15
    Officially An Architect brewbuck's Avatar
    Join Date
    Mar 2007
    Location
    Portland, OR
    Posts
    7,396
    Quote Originally Posted by Daved View Post
    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.
    Code:
    //try
    //{
    	if (a) do { f( b); } while(1);
    	else   do { f(!b); } while(1);
    //}

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. How to retrieve top 10 elements in a Dictionary
    By George2 in forum C# Programming
    Replies: 1
    Last Post: 07-23-2008, 12:12 PM
  2. Replies: 5
    Last Post: 12-05-2007, 04:39 PM
  3. Find String length and Arraysearch
    By s.rajaram in forum C Programming
    Replies: 5
    Last Post: 10-03-2007, 02:28 AM
  4. Stack functions as arrays instead of node pointers
    By sballew in forum C Programming
    Replies: 8
    Last Post: 12-04-2001, 11:13 AM
  5. Can you find the bug? 'Cause we can't
    By incognito in forum C++ Programming
    Replies: 5
    Last Post: 11-29-2001, 04:28 PM