How do I get the 10 lowest values in an array?

Question

I have an array of type double. How do I get the 10 lowest values?

double values[1000];

This is what I've come up before:

double similar[num_img];
    copy(begin(values), end(values), begin(similar)); //copy values to another variable
    int elements = sizeof(similar) / sizeof(similar[0]);
    sort(similar, similar + elements);

So that I could get the 10 values. But what I'm actually after is the indices.. So sorting it would not help, I guess.

http://stackoverflow.com/questions/1042507/finding-smallest-value-in-an-array-most-efficiently — user2485710, Feb 12 '14 at 17:16
Or iterate through, and store the lowest 10 so far as you go, for the O(n) approach. — femtoRgon, Feb 12 '14 at 17:16
@dvnrrs thought of that too.. but isn't there any other way? — joanne_, Feb 12 '14 at 17:17
"When you get rid of all impossible cases, the rest is the solution" — Dmytro Sirenko, Feb 12 '14 at 17:20
This is locked, so i have to write you the solution here. Solution no1: create a map where: the key is the number, the value is a vector with indices where the number appears in your vector. The map is sorted by the uniq keys, so there you have it: get the first 10. Solution no2. have a vector of size 10 of pairs of number and vector of indices. Go through the input vector and store only the first 10 values in this vector. — bolov, Feb 12 '14 at 17:34
Well i mean, the standard way is cleaner. Make a tmp array, sort it. Find the 10 smallest values in the tmp. Then search for those values in your array, and get your indices. — adderly, Feb 12 '14 at 17:36
using Index = std::size_t; array, 1000> values_with_indexes; int idx = 0; transform(begin(values), end(values), begin(values_with_indexes), [idx](int val) mutable { return make_pair(val, idx++); }); partial_sort(begin(values_with_indexes), begin(values_with_indexes) + 10, end(values_with_indexes), [](std::pair & a, std::pair & b) { return a.first < b.first; }); This will do it, index second part of pair. — Germán Diago, Feb 12 '14 at 17:51
@bolov: Questions that have been locked have been locked by concensus vote. It is deliberate that the answer box goes away. That doesn't mean that the comment section becomes the proper place for answers. It means the OP should read the close reason. Thanks. — Lightness Races in Orbit, Feb 12 '14 at 17:55
@LightnessRacesinOrbit I didn't provide a full answer, just a general guideline where to go from here. — bolov, Feb 12 '14 at 17:58
@LightnessRacesinOrbit it's fine! I didn't use his solution. why do u seem so mad anyway haha — joanne_, Feb 12 '14 at 17:59
@joanne_ it's not about whether you use it or not, it is whether i should have posted or not — bolov, Feb 12 '14 at 18:01

score 1 · Answer 1 · edited May 23 '17 at 12:29

1

Sort the array and grab the first 10 elements (values[0] through values[9]).

edited May 23 '17 at 12:29

Community

1
1

answered Feb 12 '14 at 17:16

TypeIA

16,916
1
38
52

this is not a valid solution, your solution doesn't cope well with multiple records with the same value and finding the "10 lowest values" it's different from finding the first or last 10 value in a sorted container. – user2485710 Feb 12 '14 at 17:18
@user2485710 The OP didn't say they had to be *distinct* values. The solution is perfectly valid, even if it's not what *you* would do / have done. Please reconsider your vote. – TypeIA Feb 12 '14 at 17:20
2

@user2485710 I don't think that's a fair call. I would take the lowest 10 values to mean the the lowest 10 elements of the given container. No distinctness requirement I'm seeing. – femtoRgon Feb 12 '14 at 17:20
@femtoRgon my vote is locked now, but I still think that the intent is to find 10 distinct values and this is not a solution. Also this is a duplicate question. – user2485710 Feb 12 '14 at 17:27

How do I get the 10 lowest values in an array?

1 Answers1