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

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.

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?

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.

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

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.

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.

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.

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?

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).

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 :).

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.