0

I want to find 3 minimum values in my matrix.

For example:

7 7 11 5 6
8 9 6 3 2 
10 15 8 3 4
12 9 6 8 11

3 minimum values: 2,3,4.

Any suggestions?

Stewie Griffin
  • 14,889
  • 11
  • 39
  • 70
mzfx
  • 73
  • 1
  • 4
  • 11

2 Answers2

3

If the vector is large, sorting a matrix (O(n*log n)) might take more time than doing three linear searches (O(n)). So something like this might actually be faster than sorting the array and selecting the first three values.

On my computer, this approach is faster on vectors larger than 1000-3000 elements.

num_vals = 3
vals = zeros(num_vals,1);
for k = 1:3
   [min_val, idx] = min(A);
   vals(ii) = min_val;
   A(idx) = NaN;
end

To illustrate:

A = rand(1e6,1);
S = A;

%% Linear search:
tic
for ii = 1:10
A = S;
num_vals = 3;
vals = zeros(num_vals,1);
for ii = 1:3
   [min_val, idx] = min(A);
   vals(ii) = min_val;
   A(idx) = NaN;
end
end
t1 = toc
A = S;

%% Sorting first:
tic
for ii = 1:10
   As = sort(A(:),'ascend');
   vals2 = As(1:3);
end
t2 = toc
isequal(vals, vals2)

t1 =
     0.0661
t2 =
     0.4781

ans =
     1
Stewie Griffin
  • 14,889
  • 11
  • 39
  • 70
  • Just keep in mind you are changing vals with this solution - if vals is an input, changing it in this case will result in a copy being made. Perhaps OP doesn't mind, but something to consider. – siliconwafer Nov 17 '14 at 13:31
  • Thanks for noting @siliconwafer. =) That's also the reason for the `A = S` line, to ensure the original vector is preserved. Maybe I should have called the vector where changes are made `A_temp` and kept the original unchanged, but ... =) – Stewie Griffin Nov 17 '14 at 15:03
  • @OP: I just noticed (when editing) you had a matrix and not a vector as it looked like at first. Then you need to do: `[min_val, idx] = min(A(:));` – Stewie Griffin Nov 17 '14 at 15:05
1

Something like this:

nrItems = 3;
yourAr  = [ 7 7 11 5 6 8 9 6 3 2 10 15 8 3 4 12 9 6 8 11 ];
sortAr  = sort(yourAr, 'ascend');


vals    = sort(1:nrItems)
Nick
  • 3,143
  • 20
  • 34