Selection algorithms

Functions
double	htm_select (double *array, size_t n, size_t k)
	Returns the k-th smallest value in an array of doubles (where k = 0 is the smallest element).
double	htm_selectmm (double *array, size_t n, size_t k)
	Finds the k-th smallest value in an array of doubles (where k = 0 is the smallest element) using the linear time median-of-medians algorithm.
double	htm_min (const double *array, size_t n)
	Returns the smallest value in an array of doubles.

---

Function Documentation

double htm_min	(	const double *	array,
		size_t	n
	)

Returns the smallest value in an array of doubles.

Assumes that:

• array != NULL
• n > 0

Parameters:

[in]	array	Array to select from.
[in]	n	Number of elements in array.

Definition at line 333 of file select.c.

double htm_select	(	double *	array,
		size_t	n,
		size_t	k
	)

Returns the k-th smallest value in an array of doubles (where k = 0 is the smallest element).

The implementation guarantees O(n) runtime even when faced with an array of identical elements. After this function returns, the k-th largest element is stored in array[k], and the following invariants hold:

• array[i] <= array[k] for i < k
• array[i] >= array[k] for i > k

Assumes that:

• array != NULL
• n > 0
• k < n

Parameters:

[in]	array	Array to select from.
[in]	n	Number of elements in array.
[in]	k	The element to select.

Definition at line 288 of file select.c.

References htm_selectmm().

double htm_selectmm	(	double *	array,
		size_t	n,
		size_t	k
	)

Finds the k-th smallest value in an array of doubles (where k = 0 is the smallest element) using the linear time median-of-medians algorithm.

Except for pathological inputs (e.g. arrays of mostly/entirely identical values or median-of-3 killer sequences), htm_select() will be faster and should be preferred. Note that htm_select() detects such pathological sequences and switches to the median-of-medians algorithm if necessary, so its runtime is also linear.

Assumes that:

• array != NULL
• n > 0
• k < n

This function has the same inputs ond enforces the same invariants as htm_select().

Definition at line 314 of file select.c.

Referenced by htm_select().