| 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
See also sort, min, max, median
|
