Quantile functions implemented in biomcmc-lib
Description of how quantile finding is implemented in the low-level phylogenetic library biomcmc-lib
002 Quantile functions implemented in biomcmc-lib
There are (as of 2019.11.29) two functions implementing the quantile finding in biomcmc-lib
: the quickselect and the Wirth algorithm.
By "quantile finding" I mean returning the k-smallest element from a vector (e.g. the median).
Both algorithms work by modifying the original vector, but in some cases biomcmc-lib
works on a copy of it:
// quickselect, copies the vector (quantile specified as fraction over n)
double biomcmc_quantile_double (double *original_vector, int n, double quantile);
// Wirth algorithm, modifies the vector (quantile specified as an integer k < n )
double biomcmc_wirth_algorithm (double *a, int n, int k);
// copies the vector and returns several quantile values at once using the Wirth algorithm
void biomcmc_quantile_vector_double (double *original_vector, int n, double *quantile, int n_quantile, double *result);
The algorithms do not interpolate, as in some median-finding algorithms — it finds the k-smallest element, therefore if there is a tie it chooses the ... smallest!
//%cflags:-lm
//%cflags: -I/usr/users/QIB_fr005/deolivl/Academic/Quadram/009.supersptree/biomcmc-lib/lib
//%cflags: -I/usr/users/QIB_fr005/deolivl/Academic/Quadram/009.supersptree/build/biomcmc-lib/lib
//%cflags: /usr/users/QIB_fr005/deolivl/Academic/Quadram/009.supersptree/build/biomcmc-lib/lib/.libs/libbiomcmc.a
#include <biomcmc.h>
int main (){
double this, unsorted[] = {1.1, 6.6, 3.3, 8.8, 7.7, 4.4, 4.3, 9.1, 5.5, 9.9};
int i;
printf ("before:\n");
for (i=0; i < 10; i++) printf ("%3.2lf ", unsorted[i]);
this = biomcmc_wirth_algorithm (unsorted, 10, 1);
printf ("\nafter finding %3.2lf (Wirth):\n", this);
for (i=0; i < 10; i++) printf ("%3.2lf ", unsorted[i]);
this = biomcmc_quantile_double (unsorted, 10, 0.2);
printf ("\nafter finding %3.2lf (quickselect):\n", this);
for (i=0; i < 10; i++) printf ("%3.2lf ", unsorted[i]);
printf ("\n");
}
biomcmc-lib commit: 5975331