Finding the n smallest items in a list
Hi there, I'm searching for a method to find the n smallest numbers in a list of m >> n numbers. The n numbers need to be sorted. m will usually be in the range of 100-1000, n will be 5 or less. So far I'm simply sorting the entire vector, which I assume is not very efficient, as the other m-n items in the container can remain unsorted. Is there a function in Boost that can help me in this situation ? Best Regards, Ruediger
Hi there,
I'm searching for a method to find the n smallest numbers in a list of m >> n numbers. The n numbers need to be sorted. m will usually be in the range of 100-1000, n will be 5 or less. So far I'm simply sorting the entire vector, which I assume is not very efficient, as the other m-n items in the container can remain unsorted. Is there a function in Boost that can help me in this situation ?
This sounds like a job for std::partial_sort. -- -- Marshall Marshall Clow Idio Software <mailto:marshall@idio.com> It is by caffeine alone I set my mind in motion. It is by the beans of Java that thoughts acquire speed, the hands acquire shaking, the shaking becomes a warning. It is by caffeine alone I set my mind in motion.
Marshall, all, thanks a lot for this hint. Works nicely (see below). Best, Ruediger /*************************************************/ #include <iostream> #include <vector> #include <algorithm> using namespace std; main() { std::vector<int> p; p.push_back(7); p.push_back(0); p.push_back(3); p.push_back(2); p.push_back(9); p.push_back(8); p.push_back(5); p.push_back(1); p.push_back(4); p.push_back(6); std::vector<int>::iterator first = p.begin(); std::vector<int>::iterator middle = first + 3; std::vector<int>::iterator last = p.end(); std::partial_sort(first, middle, last); for(std::size_t i=0; i<10; i++) { std::cout << p[i] << std::endl; } } /*************************************************/ Marshall Clow wrote:
Hi there,
n numbers. The n numbers need to be sorted. m will usually be in the range of 100-1000, n will be 5 or less. So far I'm simply sorting the entire vector, which I assume is not very efficient, as the other m-n items in the container can remain unsorted. Is there a function in Boost
I'm searching for a method to find the n smallest numbers in a list of m that can help me in this situation ?
This sounds like a job for std::partial_sort.
stl has a minheap algorithm, I believe.
-----Original Message----- From: boost-users-bounces@lists.boost.org [mailto:boost-users- bounces@lists.boost.org] On Behalf Of Ruediger Berlich Sent: Wednesday, February 04, 2009 07:59 To: boost-users@lists.boost.org Subject: [Boost-users] Finding the n smallest items in a list
Hi there,
I'm searching for a method to find the n smallest numbers in a list of m >> n numbers. The n numbers need to be sorted. m will usually be in the range of 100-1000, n will be 5 or less. So far I'm simply sorting the entire vector, which I assume is not very efficient, as the other m-n items in the container can remain unsorted. Is there a function in Boost that can help me in this situation ?
Best Regards, Ruediger
_______________________________________________ Boost-users mailing list Boost-users@lists.boost.org http://lists.boost.org/mailman/listinfo.cgi/boost-users
-- Scanned for viruses and dangerous content at http://www.oneunified.net and is believed to be clean.
-- Scanned for viruses and dangerous content at http://www.oneunified.net and is believed to be clean.
On Wed, Feb 4, 2009 at 06:58, Ruediger Berlich <ruediger.berlich@iwr.fzk.de> wrote:
I'm searching for a method to find the n smallest numbers in a list of m >> n numbers. The n numbers need to be sorted. m will usually be in the range of 100-1000, n will be 5 or less. So far I'm simply sorting the entire vector, which I assume is not very efficient, as the other m-n items in the container can remain unsorted. Is there a function in Boost that can help me in this situation ?
I don't think you even need boost: http://www.cppreference.com/wiki/stl/algorithm/partial_sort
participants (4)
-
Marshall Clow -
Ray Burkholder -
Ruediger Berlich -
Scott McMurray