quickselectFS

quickselectFS finds the k-th order statistic

expand all in page

Syntax

  • kE =quickselectFS(A,k)example
  • kE =quickselectFS(A,k,kiniindex)example
  • [kE , varargout]=quickselectFS(___)example

Description

quickselectFS is a linear algorithm equivalent to quickselect (Hoare's Find), which computes order statistics with an approach that avoids recursion and repeated calls to partitioning functions.

REMARK: we also provide the mex counterpart, quickselectFSmex; see the last example to understand how it works.

example

kE =quickselectFS(A, k) quickselectFS with all default options.

example

kE =quickselectFS(A, k, kiniindex) quickselectFS with kiniindex supplied.

example

[kE , varargout] =quickselectFS(___) quickselectFS with two output arguments.

Examples

expand all

  • quickselectFS with all default options.

    • n=200;
Y=randn(n,1);
k=10;
[out]=quickselectFS(Y,k);
% Check the result
sorY=sort(Y);
disp([out,sorY(k)])
       -1.5299   -1.5299

  • quickselectFS with kiniindex supplied.

    • n=200;
Y=randn(n,1);
k=10;
% kiniindex is supplied 
[out]=quickselectFS(Y,k,20);
% Check the result
sorY=sort(Y);
disp([out,sorY(k)])
       -1.6085   -1.6085

  • quickselectFS with two output arguments.

    • n=10;
Y=randn(n,1);
k=3;
% kiniindex is supplied 
[out,Ysor]=quickselectFS(Y,k);
% Check the result
disp([Y, Ysor])
       -0.9290   -2.0480
   -1.8365   -1.8365
    2.0429   -1.1922
   -0.8267   -0.9290
   -0.8403   -0.8403
    1.9573   -0.8267
   -1.1922    0.4189
    0.4189    0.4323
   -2.0480    1.9573
    0.4323    2.0429

    Related Examples

    expand all

  • quickselectFS: worst case scenario: see circshift.

    • n=10;
Y=1:n;
Y = circshift(Y,-1);
k=n;
out=quickselectFS(Y,k);
disp(out);
        10

  • Use the mex function quickselectFSmex.

    • REMARK 1: it is necessary to pass the number of data elements. 

    % REMARK 2: if you are looking for the order statistic k, then you
% should pass to the function k-1, as in C the array index starts from
% zero. 
% REMARK 3: it is necessary to pass a modified copy of the data  
% as indicated in the example, as the function change the
% order of the elements in the original array (array is passed by
% reference).
n=1000;
Y=randn(n,1);
k=100;
[k_star,Ysor] = quickselectFS(Y,k);
% The next line is necessary to break the link between Y and the
% copy which will be passed by reference to quickselectFSmex.
Y_copy = Y; Y_copy(end+1)=999; Y_copy(end)=[]; 
outmex = aux.quickselectFSmex(Y_copy,n,k-1);
disp('  ');
disp(['this is k_star      = ' num2str(k_star)]);
disp(['this is k_star_mex  = ' num2str(k_star)]);
% if zero, the sorted arrays are equal. 
sum(Y_copy - Y)

    Input Arguments

    expand all

    A — a set of unique numbers. Vector.

    Vector containing a set of n (distinct) numbers.

    Data Types: double

    k — order statistic index. Scalar.

    An integer between 1 and n indicating the desired order statistic.

    Data Types: double

    Optional Arguments

    kiniindex — Index of an element in A. Scalar.

    The index of an element in A that is supposed to be "close" to the desired k-th order statistic. This information is used to choose the pivot so that the chance to fall into the worst case performance ($O(n^2)$) is minimized and the average case performance is maximized.

    Example: 'kiniindex',1

    Data Types: double

    Output Arguments

    expand all

    kE —k-th order statistic. Scalar

    Element in A that is larger than exactly k - 1 other elements of A.

    varargout —Asor : Partially sorted vector. Vector

    Elements of input vector A(1:k) are sorted in ascending order. Remark: this option implies the application of a sorting algorithm on part of the array, with obvious implications on performance.

    References

    Azzini, I., Perrotta, D. and Torti, F. (2023), A practically efficient fixed-pivot selection algorithm and its extensible MATLAB suite, "arXiv, stat.ME, eprint 2302.05705"

    Riani, M., Perrotta, D. and Cerioli, A. (2015), The Forward Search for Very Large Datasets, "Journal of Statistical Software"

    See Also

    This page has been automatically generated by our routine publishFS