8

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
  • 31,767
  • 12
  • 51
  • 89
Radu094
  • 27,418
  • 16
  • 57
  • 78
  • 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
  • 102,731
  • 48
  • 279
  • 553
Karl Knechtel
  • 56,349
  • 8
  • 83
  • 124
8

This is what std::partial_sort is for.

aschepler
  • 68,873
  • 9
  • 101
  • 151
  • 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,414
  • 18
  • 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,485
  • 1
  • 24
  • 40
  • 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