Find the m-th smallest number in Matlab? [duplicate]

Question

Is there an efficient way to find the m-th smallest number in a vector of length n in Matlab? Do I have to use sort() function? Thanks and regards!

Answer 1

You don't need to sort the list of numbers to find the m^th smallest number. The m^th smallest number can be found out in linear time. i.e. if there are n elements in your array you can get a solution in O(n) time by using the selection algorithm and median of median algorithm.

The link is to the Wikipedia article,

http://en.wikipedia.org/wiki/Selection_algorithm#Linear_general_selection_algorithm_-_Median_of_Medians_algorithm

Answer 2

Edit 2: As Eitan pointed the first part of the answer doesn't address the question of finding the smallest m-th value but regarding the m-th element after the min value. The rest of the answer remains... +1 for Eitan's sharpness. While sort is probably very efficient to begin with, you can try to see whether a find will be better. For example:

id=find(X>min(X),m,'first');
id(end) % is the index of the smallest m-th element in X

the function find has added functionality that lets you find the 'first' or 'last' elements that meet some criterion. For example, if you want to find the first n elements in array X less than a value y, use find(X<y,n,'first')

This operation stops as soon as the first element meeting the condition is encountered, which can result in significant time savings if the array is large and the value you find happens to be far from the end.

I'd also like to recap what @woodchips said already in this SO discussion that is somewhat relevant to your question:

The best way to speed up basic built-in algorithms such as sort is to get a faster hardware. It will speed everything else up too. MATLAB is already doing that in an efficient manner, using an optimized code internally. Saying this, maybe a GPU add-on can improve this too...

Edit: For what it's worth, adding to Muster's comment, there is a FEX file called nth_element that is a MEX wrap of C++ that will get a solution in O(n) time for what you need. (similar to what @DDD pointed to)

Answer 3

As alternative solution, you may follow this way:

A = randi(100,4000,1);
A = sort(A,'ascend');
m = 5; % the 5 smallest numbers in array A
B = A(1:5);

I hope this helps.