---

12.3.18 Qsort functions (qsort.h)

When sorting a dataset is necessary, the C programming language provides the qsort (Quick sort) function. qsort is a generic function which allows you to sort any kind of data structure (not just a single array of numbers). To define “greater” and “smaller” (for sorting), qsort needs another function, even for simple numerical types. The functions introduced in this section are to passed onto qsort.

Note that larger and smaller operators are not defined on NaN elements. Therefore, if the input array is a floating point type, and contains NaN values, the relevant functions of this section are going to put the NaN elements at the end of the list (after the sorted non-NaN elements), irrespective of the requested sorting order (increasing or decreasing).

The first class of functions below (with TYPE in their names) can be used for sorting a simple numeric array. Just replace TYPE with the dataset’s numeric datatype. The second set of functions can be used to sort indices (leave the actual numbers untouched). To use the second set of functions, a global variable or structure are also necessary as described below.

Global variable: gal_qsort_index_single ¶

Pointer to an array (for example, float * or int *) to use as a reference in gal_qsort_index_single_TYPE_d or gal_qsort_index_single_TYPE_i, see the explanation of these functions for more. Note that if more than one array is to be sorted in a multi-threaded operation, these functions will not work as expected. However, when all the threads just sort the indices based on a single array, this global variable can safely be used in a multi-threaded scenario.

Type (C struct): gal_qsort_index_multi ¶

Structure to get the sorted indices of multiple datasets on multiple threads with gal_qsort_index_multi_d or gal_qsort_index_multi_i. Note that the values array will not be changed by these functions, it is only read. Therefore all the values elements in the (to be sorted) array of gal_qsort_index_multi must point to the same place.

struct gal_qsort_index_multi
{
  float *values;         /* Array of values (same in all).      */
  size_t  index;         /* Index of each element to be sorted. */
};

Function:
int
gal_qsort_TYPE_d (const void *a, const void *b) ¶

When passed to qsort, this function will sort a TYPE array in decreasing order (first element will be the largest). Please replace TYPE (in the function name) with one of the Numeric data types, for example, gal_qsort_int32_d, or gal_qsort_float64_d.

Function:
int
gal_qsort_TYPE_i (const void *a, const void *b) ¶

When passed to qsort, this function will sort a TYPE array in increasing order (first element will be the smallest). Please replace TYPE (in the function name) with one of the Numeric data types, for example, gal_qsort_int32_i, or gal_qsort_float64_i.

Function:
int
gal_qsort_index_single_TYPE_d (const void *a, const void *b) ¶

When passed to qsort, this function will sort a size_t array based on decreasing values in the gal_qsort_index_single. The global gal_qsort_index_single pointer has a void * pointer which will be cast to the proper type based on this function: for example gal_qsort_index_single_uint16_d will cast the array to an unsigned 16-bit integer type. The array that gal_qsort_index_single points to will not be changed, it is only read. For example, see this demo program:

#include <stdio.h>
#include <stdlib.h>           /* qsort is defined in stdlib.h. */
#include <gnuastro/qsort.h>

int
main (void)
{
  size_t s[4]={0, 1, 2, 3};
  float f[4]={1.3,0.2,1.8,0.1};
  gal_qsort_index_single=f;
  qsort(s, 4, sizeof(size_t), gal_qsort_index_single_float_d);
  printf("%zu, %zu, %zu, %zu\n", s[0], s[1], s[2], s[3]);
  return EXIT_SUCCESS;
}

The output will be: 2, 0, 1, 3.

Function:
int
gal_qsort_index_single_TYPE_i (const void *a, const void *b) ¶

Similar to gal_qsort_index_single_TYPE_d, but will sort the indexes such that the values of gal_qsort_index_single can be parsed in increasing order.

Function:
int
gal_qsort_index_multi_d (const void *a, const void *b) ¶

When passed to qsort with an array of gal_qsort_index_multi, this function will sort the array based on the values of the given indices. The sorting will be ordered according to the values pointer of gal_qsort_index_multi. Note that values must point to the same place in all the structures of the gal_qsort_index_multi array.

This function is only useful when the indices of multiple arrays on multiple threads are to be sorted. If your program is single threaded, or all the indices belong to a single array (sorting different sub-sets of indices in a single array on multiple threads), it is recommended to use gal_qsort_index_single_d.

Function:
int
gal_qsort_index_multi_i (const void *a, const void *b) ¶

Similar to gal_qsort_index_multi_d, but the result will be sorted in increasing order (first element will have the smallest value).