9

I need to sort the elements in a std::vector, but I'm only interested in the top N items being sorted, not the entire list:

E.g. in a list of 10 elements, only first 3 have to be sorted. Don't care about the rest...

1,2,3,6,7,4,9,8,5

Can this be done using std::sort?

Edit

I simply needed to find the top N items in a vector. std::partial_sort_copy was exactely what I needed.

aschipfl
  • 33,626
  • 12
  • 54
  • 99
Radu094
  • 28,068
  • 16
  • 63
  • 80
  • 1
    This is a vague question - do you only want first three items to be sorted? Or to have three smallest elements of the whole list sorted at the beginning? – Karel Petranek Dec 08 '10 at 19:23
  • Maybe you'd want to take a look at this : http://stackoverflow.com/questions/217073/partial-sort-of-stdlist – Pacane Dec 08 '10 at 19:24
  • If you got your question answered, **accept** the answer instead of editing the question to repeat the answer. – jalf Dec 08 '10 at 19:51

4 Answers4

15

Try std::partial_sort instead of std::sort. :)

einpoklum
  • 118,144
  • 57
  • 340
  • 684
Karl Knechtel
  • 62,466
  • 11
  • 102
  • 153
8

This is what std::partial_sort is for.

aschepler
  • 70,891
  • 9
  • 107
  • 161
  • Your link says the initial part will be sorted: "the subrange [first,middle) contains the smallest elements of the entire range sorted in ascending order" – Lou Franco Dec 08 '10 at 19:30
  • Thanks Lou. I had `partial_sort` and `partition` confused in my head. – aschepler Dec 08 '10 at 19:33
3

If you require ordering then partial_sort will do it, otherwise if you only need to partition the range nth_element will do it faster.

Gene Bushuyev
  • 5,512
  • 20
  • 19
0

Just tell the sort routine where you want to stop sorting:

std::vector<int> values;
for (int i = 0; i < 10; ++i)
    values.push_back(rand() % 10);

std::cout << "UNSORTED" << endl;
std::copy(values.begin(), values.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;

std::cout << "SORTED (Partially)" << std::endl;
std::sort(values.begin(), values.begin() + 3);
std::copy(values.begin(), values.end(), std::ostream_iterator<int>(std::cout, " "));
std::cout << std::endl;
Zac Howland
  • 15,777
  • 1
  • 26
  • 42
  • 3
    Granted, the question as originally asked was very unclear, but it's now clear that the top 3 elements of the *entire* vector are needed, so your approach won't work. – j_random_hacker Nov 03 '11 at 14:18