BatchSort< T extends MultiDimComparable<? super T > Class Template Reference

This class implements a MultiDimSortComparable that performs a batch sort on multivariate arrays. More...

Inheritance diagram for BatchSort< T extends MultiDimComparable<? super T >:

Collaboration diagram for BatchSort< T extends MultiDimComparable<? super T >:

Public Member Functions
	BatchSort (int[] batchNumbers)
	Constructs a BatchSort that will always use the (fixed) batch numbers given in batchNumbers. More...
	BatchSort (double[] batchExponents)
	Constructs a BatchSort that will use the proportion exponents in batchExponents, which must contain non-negative numbers that sum to 1. More...
void	setBatchNumbers (int n)
	Resets the corresponding vector of batch numbers for the given number \(n\) of objects. More...
void	setBatchExponents (double[] batchExponents)
	Sets the vector of proportion exponents \(\alpha_0,\alpha_1,…,\alpha_{d-1}\) to the values in batchExponents. More...
int []	getBatchNumbers ()
	Returns the current vector of batch numbers \(n_j\).
int	getBatchProduct ()
	Returns the product \(p\) of current batch numbers.
double []	getBatchExponents ()
	Returns the current vector of batch exponents \(\alpha_j\).
int	dimension ()
void	sort (T[] a, int iMin, int iMax)
	Sorts the subarray a[iMin..iMax-1] using this batch sort.
void	sort (T[] a)
	Sorts the entire array.
void	sort (double[][] a, int iMin, int iMax)
	Sorts the subarray a[iMin..iMax-1] using this batch sort.
void	sort (double[][] a)
	Sorts the entire array.

Package Attributes
int	dimension
boolean	useExponents
int []	batchNumbers
double []	batchExponents
int	batchProduct = 1
int	nSaved = 0

Detailed Description

This class implements a MultiDimSortComparable that performs a batch sort on multivariate arrays.

It separates the objects in \(n_0\) batches of (approximately) equal size such that each object in a batch is smaller or equal, in the first coordinate, to the objects in the next batches. Then, each batch is separated in \(n_1\) batches in the same way but using the second coordinate. And so on.

One way of constructing a BatchSort object is to specify the batch numbers (integers) \(n_0, n_1, …, n_{d-1}\) in an array of size \(d\) named batchNumbers passed to the constructor. The size \(d\) must not exceed the dimension of the objects to be sorted, and the product \(p = n_0 n_1 \cdots n_{d-1}\) must normally be equal to the number \(n\) of objects to be sorted, which is iMax - iMin when doing a partial sort, and the total number of objects otherwise. This means that one should normally use always the same \(n\) after the BatchSort object has been constructed in this way, with a fixed \(p\). The sorting method always uses batch sizes at each level as if the number of objects was exactly \(p\). The batch size at level \(j\) is \(n_{j+1} \cdots n_{d-1}\). If there are less than \(p\) objects, some batches (the last ones) can have fewer objects or be empty. What is done is conceptually equivalent to adding dummy objects at the end of the array so their total number is exactly \(p\). For example, if \(n_0 = 3\), \(p=15\) and \(n=13\), then the batch size will be \(15/3 = 5\) but the last batch will have only 3 objects. The value of \(n_{d-1}\) is actually never used by the batch sort; at the last level, each batch is sorted by the last coordinate regardless of its size.

A second way of constructing a BatchSort object is by specifying an array of non-negative doubles \(\alpha_0,\alpha_1,…,\alpha_{d-1}\), called proportion exponents, such that \(\alpha_0+\cdots+\alpha_{d-1} = 1\). For each number \(n\) of objects to be sorted, the batch numbers will be recomputed as (approximately) \(n_j = n^{\alpha_j}\). With this construction, one can easily handle very different (arbitrary) values of \(n\) with the same BatchSort object. The vector of batch numbers is recomputed each time we sort with a new value of \(n\), as follows: \(n_0 = \lceil n^{\alpha_0} \rceil\), \(n_1 = \lceil(n/n_0)^{\alpha_1} \rceil\), …, \(n_{d-1} = \lceil n / (n_0 \cdots n_{d-2}) \rceil\). These values are saved in case we use the same \(n\) the next time. They give \(p = n_0 \cdots n_{d-1} \ge n\). The batch size at level \(j\) is again \(n_{j+1} \cdots n_{d-1}\). When \(n < p\), some batches (the last ones) have fewer objects than the others.

Constructor & Destructor Documentation

BatchSort() [1/2]

BatchSort

(

int []

batchNumbers

)

Constructs a BatchSort that will always use the (fixed) batch numbers given in batchNumbers.

These batch numbers can be changed only by creating new object, of by using proportion exponents via setBatchExponents. The number of objects to sort should not exceed the product of the numbers in batchNumbers.

Parameters

batchNumbers

number of batches in each dimension

BatchSort() [2/2]

BatchSort

(

double []

batchExponents

)

Constructs a BatchSort that will use the proportion exponents in batchExponents, which must contain non-negative numbers that sum to 1.

Parameters

batchExponents

proportion exponents to compute the batches sizes

Member Function Documentation

setBatchExponents()

void setBatchExponents

(

double []

batchExponents

)

Sets the vector of proportion exponents \(\alpha_0,\alpha_1,…,\alpha_{d-1}\) to the values in batchExponents.

These values must be non-negative and sum to 1. From now on, this BatchSort object will use proportion exponents.

Parameters

batchExponents

exponents in each dimension

setBatchNumbers()

void setBatchNumbers

(

int

n

)

Resets the corresponding vector of batch numbers for the given number \(n\) of objects.

This method can be invoked only when proportion exponents are used and have been defined previously.

Parameters

n	number of objects

---

The documentation for this class was generated from the following file:

• BatchSort.java