Next: , Previous: Sorting vectors, Up: Sorting

11.3 Selecting the k smallest or largest elements

The functions described in this section select the k smallest or largest elements of a data set of size N. The routines use an O(kN) direct insertion algorithm which is suited to subsets that are small compared with the total size of the dataset. For example, the routines are useful for selecting the 10 largest values from one million data points, but not for selecting the largest 100,000 values. If the subset is a significant part of the total dataset it may be faster to sort all the elements of the dataset directly with an O(N \log N) algorithm and obtain the smallest or largest values that way.

— Function: void gsl_sort_smallest (double * dest, size_t k, const double * src, size_t stride, size_t n)

This function copies the k smallest elements of the array src, of size n and stride stride, in ascending numerical order into the array dest. The size k of the subset must be less than or equal to n. The data src is not modified by this operation.

— Function: void gsl_sort_largest (double * dest, size_t k, const double * src, size_t stride, size_t n)

This function copies the k largest elements of the array src, of size n and stride stride, in descending numerical order into the array dest. k must be less than or equal to n. The data src is not modified by this operation.

— Function: void gsl_sort_vector_smallest (double * dest, size_t k, const gsl_vector * v)
— Function: void gsl_sort_vector_largest (double * dest, size_t k, const gsl_vector * v)

These functions copy the k smallest or largest elements of the vector v into the array dest. k must be less than or equal to the length of the vector v.

The following functions find the indices of the k smallest or largest elements of a dataset,

— Function: void gsl_sort_smallest_index (size_t * p, size_t k, const double * src, size_t stride, size_t n)

This function stores the indices of the k smallest elements of the array src, of size n and stride stride, in the array p. The indices are chosen so that the corresponding data is in ascending numerical order. k must be less than or equal to n. The data src is not modified by this operation.

— Function: void gsl_sort_largest_index (size_t * p, size_t k, const double * src, size_t stride, size_t n)

This function stores the indices of the k largest elements of the array src, of size n and stride stride, in the array p. The indices are chosen so that the corresponding data is in descending numerical order. k must be less than or equal to n. The data src is not modified by this operation.

— Function: void gsl_sort_vector_smallest_index (size_t * p, size_t k, const gsl_vector * v)
— Function: void gsl_sort_vector_largest_index (size_t * p, size_t k, const gsl_vector * v)

These functions store the indices of the k smallest or largest elements of the vector v in the array p. k must be less than or equal to the length of the vector v.