Header Sort.h

Detailed Description

Provides routines for sorting, indexing, and ranking real vector elements.

Synopsis

#include <lal/Sort.h>

Description

Heap Sort

These routines sort a vector *data (of type REAL4Vector or REAL8Vector) into ascending order using the in-place heapsort algorithm, or construct an index vector *index that indexes *data in increasing order (leaving *data unchanged), or construct a rank vector *rank that gives the rank order of the corresponding *data element.

The relationship between sorting, indexing, and ranking can be a bit confusing. One way of looking at it is that the original array is ordered by index, while the sorted array is ordered by rank. The index array gives the index as a function of rank; i.e. if you're looking for a given rank (say the 0th, or smallest element), the index array tells you where to look it up in the unsorted array:

unsorted_array[index[i]] = sorted_array[i]

The rank array gives the rank as a function of index; i.e. it tells you where a given element in the unsorted array will appear in the sorted array:

unsorted_array[j] = sorted_array[rank[j]]

Clearly these imply the following relationships, which can be used to construct the index array from the rank array or vice-versa:

index[rank[j]] = j
rank[index[i]] = i

The XLAL versions of these routines, XLALHeapSort(), XLALHeapIndex(), and XLALHeapRank(), perform the same operations but on arrays of nobj generic objects of size size pointed to by base and using the comparison function compar. The function compar() has the prototype

int compar( void *p, const void *x, const void *y )

and returns \(-1\) if \({\mathtt{x}}<{\mathtt{y}}\), \(0\) if \({\mathtt{x}}={\mathtt{y}}\), and \(+1\) if \({\mathtt{x}}>{\mathtt{y}}\). Here p (which may be NULL) is a pointer to additional data that may be used in the comparison function. This pointer is passed to the comparison function unchanged from the argument params of XLALHeapSort(), XLALHeapIndex(), and XLALHeapRank().

Insertion Sort

This is provided so the frame file cache handling code could have access to a sort algorithm that has the property that the original element order is preserved in the case of ties, a feature it relies on for proper treatment of cache files containing redundant fail-over copies. The C library's qsort() does not guarantee that order is preserved. This function is not fast, it just is what it is.

Merge Sort

This is also a stable sort algorithm, faster than insertion sort, but requires more temporary memory.

Search Sorted

The routine XLALIsSorted() returns \(1\) if the array is sorted (in ascending order) or \(0\) otherwise. To determine if an array is sorted in descending order, reverse the arguments in the compar routine.

The routine XLALSearchSorted() returns the index in which the element given by key should be inserted in order to maintain the sort order.

If \({\mathtt{side}} < 0\) then the index to insert is on the left:

a[i-1] < v <= a[i]

If \({\mathtt{side}} > 0\) then the index to insert is on the right:

a[i-1] <= v < a[i]

If \({\mathtt{side}} = 0\) then the index is that of a matching element:

a[i] == v

or \(-1\) is returned if there is no matching element.

Algorithm

Heap Sort

These routines use the standard heap sort algorithm described in Sec. 8.3 of Ref. [22] .

The LALSHeapSort() and LALDHeapSort() routines are entirely in-place, with no auxiliary storage vector. The LALSHeapIndex() and LALDHeapIndex() routines are also technically in-place, but they require two input vectors (the data vector and the index vector), and leave the data vector unchanged. The LALSHeapRank() and LALDHeapRank() routines require two input vectors (the data and rank vectors), and also allocate a temporary index vector internally; these routines are therefore the most memory-intensive. All of these algorithms are \(N\log_2(N)\) algorithms, regardless of the ordering of the initial dataset.

Note: if you can use qsort(), you should.

Prototypes
int	XLALHeapSort (void *base, UINT4 nobj, UINT4 size, void *params, int(*compar)(void *, const void *, const void *))
int	XLALHeapIndex (INT4 *indx, void *base, UINT4 nobj, UINT4 size, void *params, int(*compar)(void *, const void *, const void *))
int	XLALHeapRank (INT4 *rank, void *base, UINT4 nobj, UINT4 size, void *params, int(*compar)(void *, const void *, const void *))
int	XLALInsertionSort (void *base, size_t nobj, size_t size, void *params, int(*compar)(void *, const void *, const void *))
int	XLALMergeSort (void *base, size_t nobj, size_t size, void *params, int(*compar)(void *, const void *, const void *))
int	XLALIsSorted (void *base, size_t nobj, size_t size, void *params, int(*compar)(void *, const void *, const void *))
ssize_t	XLALSearchSorted (const void *key, const void *base, size_t nobj, size_t size, void *params, int(*compar)(void *, const void *, const void *), int side)

Files
file	SortTest.c
	A program to test sorting routines.

Function Documentation

XLALHeapSort()

int XLALHeapSort	(	void *	base,
		UINT4	nobj,
		UINT4	size,
		void *	params,
		int(*)(void *, const void *, const void *)	compar
	)

See also

See Header Sort.h for documentation

Definition at line 44 of file HeapSort.c.

XLALHeapIndex()

int XLALHeapIndex	(	INT4 *	indx,
		void *	base,
		UINT4	nobj,
		UINT4	size,
		void *	params,
		int(*)(void *, const void *, const void *)	compar
	)

See also

See Header Sort.h for documentation

Definition at line 98 of file HeapSort.c.

XLALHeapRank()

int XLALHeapRank	(	INT4 *	rank,
		void *	base,
		UINT4	nobj,
		UINT4	size,
		void *	params,
		int(*)(void *, const void *, const void *)	compar
	)

See also

See Header Sort.h for documentation

Definition at line 152 of file HeapSort.c.

XLALInsertionSort()

int XLALInsertionSort	(	void *	base,
		size_t	nobj,
		size_t	size,
		void *	params,
		int(*)(void *, const void *, const void *)	compar
	)

See also

See Header Sort.h for documentation

Definition at line 37 of file InsertionSort.c.

XLALMergeSort()

int XLALMergeSort	(	void *	base,
		size_t	nobj,
		size_t	size,
		void *	params,
		int(*)(void *, const void *, const void *)	compar
	)

See also

See Header Sort.h for documentation

Definition at line 36 of file MergeSort.c.

XLALIsSorted()

int XLALIsSorted	(	void *	base,
		size_t	nobj,
		size_t	size,
		void *	params,
		int(*)(void *, const void *, const void *)	compar
	)

See also

See Header Sort.h for documentation

Definition at line 17 of file SearchSorted.c.

XLALSearchSorted()

ssize_t XLALSearchSorted	(	const void *	key,
		const void *	base,
		size_t	nobj,
		size_t	size,
		void *	params,
		int(*)(void *, const void *, const void *)	compar,
		int	side
	)

See also

See Header Sort.h for documentation

Definition at line 31 of file SearchSorted.c.