# quickselectFS

quickselectFS finds the k-th order statistic

## 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.

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

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

 [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 = 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

### 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

### 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

### 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.

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"