Find n minimum values in an array?

I have an array, I need to be able to select 2, or 4 or so on 'n' minimum (smallest) values from the specific array? I know i can use 'min' function but this only gives one smallest value. I do not want to sort the array in order and pick values. is there another way ?????

[Guillaume]

I do not want to sort the array

Finding the n smallest values in a set is by definition imposing an order on that set. That is call 'sorting'.

A solution that does not involve a call to sort is bound to be several orders of magnitude slower and only of academic interest.

[Margarida Costa]

And is there an easy way to get back the indexes of those values?

[Nicholas Ayres]

The "optional second output" of sort is the index order.

[sortedVals,indexes] = sort(myvals);

So

myVals = [1 0.1 7 10 4];
[sortedVals,indexes] = sort(myVals);

gives

sortedVals = [0.1 1 4 7 10]
indexes = [2 1 5 3 4]

Figured I'd pop this here in case anyone else comes along with the same question. :)

Answer 1

[Titus Edelhofer]

Hi,

if you don't want to sort, and n is not too large, you could remove the index, something like

x = rand(1000, 1);
n = 5;
val = zeros(n,1);
for i=1:n
  [val(i),idx] = min(x);
  % remove for the next iteration the last smallest value:
  x(idx) = [];
end

Titus

[ME]

Thank you

[Guillaume]

And as noted in my comment to the question, the solution is several orders of magnitude slower than using sort:

>>x = rand(1000, 1)
>>n = 5;

>>tic; val = zeros(n, 1); for i=1:n; [val(i), idx] = min(x); x(idx) = []; end; toc
Elapsed time is 0.001408 seconds

>>tic; xs = sort(x); val=xs(1:n); toc
Elapsed time is 0.000084 seconds

16 times slower than sort, and more lines of code to boot. What's the point?

[James Tursa]

Slower because this line copies the entire data set (except one element) at each iteration:

x(idx) = [];

Generally a bad thing to do because of the speed consequences as Guillaume points out.

[Rik]

I know this is an old thread, but still:

Even replacing x(idx) with NaN instead of removing the entry doesn't really improve the speed. This might be dependent on the release and of the size of the input array.

[zaid tahir]

@Titus Edelhoferthanks for the code. Helped make a very complex problem, very simple.

Answer 2

[Jan]

While sorting is the best approach to get the data, you can easily obtain an unsorted result:

n = 2;
[xs, index] = sort(x);
result      = x(sort(index(1:n)))

[Chris Volpe]

Seems to me you want to leave out the "sort" call in line 3:

result = x(index(1:n))

Answer 3

[Salam Ismaeel]

use: mink() command for R2018a

https://www.mathworks.com/help/matlab/ref/mink.html

[M Waqar Nadeem]

This helped me in my problem, thanks

[Bill Tubbs]

This is the correct answer. Thanks!

Example:

>> X = [4 1 2 1 5 4 2];
>> [minValues, idx] = mink(X,3)

minValues =

     1     1     2


idx =

     2     4     3

[Martin Vankát]

Thank you! This one helped.

Answer 4

[Titus Edelhofer]

Hi,

if it's not floating point but integers (so no problem with roundoff),you could do the following:

x = [1 3 2 4 1 3 5 4 1 3 1]
% find the first 2 min occurrences:
idxMin = find(x==min(x), 2, 'first')

This tells that the smallest value 1 is found at positions 1 and 5. Or are you looking for the n smallest values in the sense, you are looking for the smallest, the second smallest etc.? In this case the answer is simply

n = 2;
xs = sort(x);
% pick the n smallest:
xs(1:n)

Titus

[ME]

hi that just gave me 1 and 5 as an answer

[Titus Edelhofer]

I think I misunderstood what you are looking for, see edited answer.

[ME]

thanks

[Titus Edelhofer]

If this was what you were looking for, then please mark the question as answered ... Thanks, Titus

[ME]

not entirely, because i don't want to sort the array.

Answer 5

[Luis Gomez]

I do it like this,

% k miminum values of a matrix (return the position, not the value)
% not optimized: it just worked for my application.
a = magic(5)

a = 5×5

17 24 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 18 25 2 9

%Copy the original data
aa = a;
%Size of the matrix
[rows columns] = size(a);
%Select the k mininum values
k = 3;

k_mins = zeros(k,1); %to store solution (not really needed)
for i = 1: k
    [m, I] = min(a(:));
    a(I) = inf;
    k_mins(i) = I;
end
k_mins

k_mins = 3×1

11 20 24

% to get the [i, j] usual matrix locations for ecah value within k_mins
% for instance, to get the "i,j" indices por first element of k_mins
% vector,
[i j] = ind2sub([rows, columns],k_mins(1))

i = 1

j = 3

%the value
aa(i,j)

ans = 1

[Rik]

Your code doesn't work, and it is slower than other solutions.

% k miminum values of a matrix
a = 1e101*magic(5) % contrived example

a = 5×5

1.0e+102 * 1.7000 2.4000 0.1000 0.8000 1.5000 2.3000 0.5000 0.7000 1.4000 1.6000 0.4000 0.6000 1.3000 2.0000 2.2000 1.0000 1.2000 1.9000 2.1000 0.3000 1.1000 1.8000 2.5000 0.2000 0.9000

%Select the k mininum values
k = 3;
k_m = zeros(3);
for i = 1: k
    [m I] = min(a(:));
    a(I) = 1e100;
    k(i) = I;
end
k

k = 1×3

11 11 11

You can solve this by changing your flag value to inf instead of 1e100.

But even then. What are you doing with k_m? Is it supposed to store the k results? Why isn't it created as zeros(1,k)? Why are you storing the indices in k, and not the values m?

[Luis Gomez]

It is true that it can be slow for large matrices (I work with small matrices).

The "k" ihdices just locate the values you want. For instance, for the example I put,

k = [11 20 24], which are just the a(11), a(20) and a(24) values of the original a matrix, that is,

a(11) = 1,

a(20) = 2,

a(24) = 24.

It works fine for my application. I tried on a a = magic(100), and k = 22, and got results "instantly", so, it seems that is not bad!

[Luis Gomez]

I correctted some minor bugs (thanks to the one that pointed it out!).

[Rik]

I'm of the opinion you shouldn't wait for performance to become an issue before you look for optimizations. Good should not be the enemy of better. If you make them a habit, you will have a lot less work once performance does become important. One important part is why you serialize inside the loop. For large k, you will do this operation many times, and it is really not necessary.

It is also a good idea to look at what mlint is suggesting. It is suggesting you put a comma between m and I. I see no reason why you wouldn't.

I also don't see where you are actually returning the lowest values. They aren't in k_mins (despite its name), because that only stores the indices. The actual minimum values require an extra step, which is made impossible due the overwriting, as you can see below.

So, putting your code in a function with the two adjustments:

% k miminum values of a matrix
a = magic(5)

a = 5×5

17 24 1 8 15 23 5 7 14 16 4 6 13 20 22 10 12 19 21 3 11 18 25 2 9

%Select the k mininum values
k = 3;

find_k_lowest_values(a,k)

ans = 3×1

Inf Inf Inf

% show time spent in microseconds on this example
1e6*timeit(@() find_k_lowest_values(a,k))

ans = 14.8830

1e6*timeit(@() find_k_lowest_values__alternative(a,k))

ans = 6.3830

function k_lowest_values=find_k_lowest_values(a,k)
% Write single line purpose here
%
% Explain the function and the available syntax options.
% This help text should ensure you never *have* to look at the code itself.

% A comment should explain what is stored in k_mins
k_mins = zeros(k,1);
for i = 1: k
    % A comment should explain why we serialize inside the loop
    [~,I] = min(a(:));
    % A comment should explain why we set this value to inf
    a(I) = inf;
    k_mins(i) = I;
end
% A comment should explain why we do this
k_lowest_values=a(k_mins);
end

If you insist on a loop, I would suggest this:

function k_lowest_values=find_k_lowest_values__alternative(a,k)
% Write single line purpose here
%
% Explain the function and the available syntax options.
% This help text should ensure you never *have* to look at the code itself.

% We only need the data inside a, the shape is not important. By converting
% to a vector we can use min() inside the loop.
a=a(:);

% Pre-allocate the output.
k_lowest_values = zeros(k,1);
for n = 1:k
    % Store the lowest value in the output and get the index.
    [k_lowest_values(n),ind] = min(a);
    % Replace the position of the lowest value with inf to ignore it on the
    % next iteration.
    a(ind) = inf;
end
end

[Luis Gomez]

Thanks a lot for your comments. Indeed, as I explained before, it was something I did "on the shelf" and dit not worried more for other format issues.

Note that each element within the k_mins vector can be recovered with the usual [i,j] indices through the matlab function,

(for instance, the element 11 of the matrix)

[i j] = ind2sub([m n],11)

with

[m,n] = size(a)

[Rik]

Well, as I showed in my comment, your code did not actually return the values, only the indices. Since the positions were by that point overwritten by inf, those were useles. You need to store the value that min returns.

The question was how to find the smallest k values. Why are you leaving the retrieval of those values as an excersize to the reader? Neither linear indices, or cartesian indices are relevant as far as I can tell. It is a valid thing to want, but why post it as an answer if it isn't?

Your comments are already improved compared to your intial post, but you should consider making it a function with documentation. That will also show you that you're not using m.

And you still haven't explained why you insist on using this loop, instead of a solution based on sort.

[Walter Roberson]

Why not mink()?

[Rik]

@Walter, to be honest I always forget that function exists ever since it was introduced in R2017b.