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");
}

before:
1.10 6.60 3.30 8.80 7.70 4.40 4.30 9.10 5.50 9.90 
after finding 3.30 (Wirth):
1.10 3.30 4.30 4.40 5.50 7.70 

biomcmc-lib commit: 5975331