Code covered by the BSD License

### Highlights from KTHVALUE (v2.1, jun 2012)

5.0

5.0 | 1 rating Rate this file 3 Downloads (last 30 days) File Size: 2.77 KB File ID: #23195

# KTHVALUE (v2.1, jun 2012)

05 Mar 2009 (Updated 02 Jul 2012)

select the k-th smallest element in a (randomized) list

File Information
Description

KTHVALUE - select the k-th smallest element in a (randomized) list

V = KTHVALUE(L,K) returns the K-th smallest number from a list. L is
(unordered) list of N values, and K is a scalar between 1 and N.

Example:
L = ceil(10*rand(1,6)), K = 3
V = kthvalue(L,K)

The result is equivalent to picking the K-th value in the sorted list
"sort(L)". However, KTHVALUE does not require the explicit creation of
a temporary array, and is often faster.

L = rand(10000,1000) ; K = ceil(numel(L)/2) ;
tic ; V1 = kthvalue(L,K) ; toc
% Elapsed time is 0.73 seconds. (on average)
tic ; B = sort(L(:)) ; V2 = B(K) ; toc ;
% Elapsed time is 1.79 seconds.
isequal(V1,V2) % of course ...

Notes:
- Despite its nice algorithm, I would recommend the approach using SORT
over KTHVALUE, primarily because with one call to SORT one can
extract multiple elements.
- To find the k-th largest element, use -KTHVALUE(-L,K)
- For lists L with (2*K-1) numbers, KTHVALUE(L,K) equals the median
value of L.
- KTHVALUE can be used as a (rather inefficient ;-) ) sorting algorithm:
A = rand(5,1) ;
sortedA = zeros(size(A)) ;
for i=1:numel(A),
sortedA(i) = kthvalue(A,i) ;
end
[sort(A) sortedA]

For some more ideas on element selection see
http://en.wikipedia.org/wiki/Selection_algorithm

MATLAB release MATLAB 6.5 (R13)
06 Apr 2009

@Luigi: To be honest, I suggest that you use SORT in all cases ... the gain in using KTHVALUE is small. And it is not so much the value of K that determines its running time. This submission is to be regarded as a programming exercise.

05 Apr 2009

Nice One,

Well commented and written,

it is also fast for high K/Numel(L) ratio, but I thing for a smaller K, 1-2-3 , brute search would be faster.

So if I can suggest an improvement I would switch to brute search in those cases. Am I wrong?