BatchSortPow2 Class Reference

This is a subclass of BatchSort for which the batch numbers \(n_j\) are always powers of 2. More...

Inheritance diagram for BatchSortPow2:

Collaboration diagram for BatchSortPow2:

Public Member Functions
	BatchSortPow2 (double[] batchExponents)
	Constructs a BatchSortPow2 that will use proportion exponents in batchExponents, which must contain non-negative numbers that sum to 1. More...
void	setBatchNumbers (int n)
	For a number \(n\) of objects and a predefined vector of proportion exponents \(\alpha_0,\alpha_1,…,\alpha_{d-1}\), computes and sets the corresponding vector of batch numbers, for which each batch number is a power of 2 and their product is \(p = 2^e \ge n\). More...
int []	getBitNumbers ()
	Returns the current vector of integers \(e_j\).
Public Member Functions inherited from BatchSort< T extends MultiDimComparable<? super T >
	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 []	ej
Package Attributes inherited from BatchSort< T extends MultiDimComparable<? super T >
int	dimension
boolean	useExponents
int []	batchNumbers
double []	batchExponents
int	batchProduct = 1
int	nSaved = 0

Detailed Description

This is a subclass of BatchSort for which the batch numbers \(n_j\) are always powers of 2.

One has \(n_j = 2^{e_j}\) for all \(j\) and \(p = 2^e\), where the \(e_j\) and \(e\) are integers.

The batch numbers can only be specified via the proportion exponents \(\alpha_0,\alpha_1,…,\alpha_{d-1}\). The \(e_j\) are computed as a function of the number \(n\) of objects to be sorted. This number \(n\) is first rounded up the nearest power of 2, say \(p = 2^e \ge n\). (Often, it should already be a power of 2.) Then the \(e_j\) are defined as \(e_0 = \lceil e \alpha_0 \rceil\) and \(e_j = \lceil(e - e_0 - \cdots- e_{j-1}) (\alpha_0 + \cdots+ \alpha_j) \rceil\) for \(1\le j < d\). This gives \(e_0 + \cdots+ e_{d-1} = e\).

Constructor & Destructor Documentation

BatchSortPow2()

BatchSortPow2

(

double []

batchExponents

)

Constructs a BatchSortPow2 that will use 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

setBatchNumbers()

void setBatchNumbers

(

int

n

)

For a number \(n\) of objects and a predefined vector of proportion exponents \(\alpha_0,\alpha_1,…,\alpha_{d-1}\), computes and sets the corresponding vector of batch numbers, for which each batch number is a power of 2 and their product is \(p = 2^e \ge n\).

Parameters

n	number of objects

---

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

• BatchSortPow2.java