QuickSelect

The SDL Component Suite is an industry leading collection of components supporting scientific and engineering computing. Please visit the SDL Web site for more information....

Home

QuickSelect

QuickSelect

Unit:	SDL_math1
Class:	none
Declaration:	[1] function QuickSelect (var Data: array of double; k, First, Last: integer): double; [2] function QuickSelect (var Data: array of double; k, First, Last: integer; AbundantVal: double): double;

The function QuickSelect returns the value of the k^th smallest element of the unsorted array Data and can be used to calculate a particular quantile of a set of values. The parameter k specifies the rank number of the order statistic, the parameters First and Last specify the indices of the first and the last element of the data array to be included in the calculation (valid range is from 0 to length(Data)-1).

If the array Data contains a high number (more than 50%) of equal values version [1] becomes prohibitively slow at high k values. In this case version [2] can be used to speed up the calculation by specifying the abundant value by the parameter AbundantVal. Please note that the speed of QuickSelect depends on the distribution of the values, the number of data values (difference between Last and First) and on k. Thus it is recommended to test whether version [1] or version [2] behaves faster in a particular situation.

Hint: Please note that version [1] of the function QuickSelect changes the sequence of the values in the array Data (version [2] does not).

Example: In order to calculate the 95-percentile of the first 100 values in the data array one has to execute the following statement:
perc95 := QuickSelect (data, round(0.95*(Last-First+1)), 0, 99);

The function QuickSelect is much faster than the calculation of quantiles by means of a full sort of the data array. The only drawback is that QuickSelect can calculate only one particular quantile at a time. See the Delphi Bits blog for additional information.

Last Update: 2023-Jul-30