umontreal.iro.lecuyer.util

Class BatchSort

java.lang.Object

umontreal.iro.lecuyer.util.BatchSort

All Implemented Interfaces:

MultiDimSort

public class BatchSort
extends java.lang.Object
implements MultiDimSort

This class implements a MultiDimSort that performs a batch sort on the arrays.

For MultiDimComparable objects, the dimension mentioned below refers to the value returned by dimension. The ordering of the elements is the one induced by the method compareTo.

The batch sort separates the objects in n₁ batches of equal size such that each object in a batch is smaller or equal, in dimension 1, to the objects in the next batches. Then, each batch is separated in n₂ batches the same way but in dimension 2. And so on. The integers n₁, n₂,…, n_d are given in the array batches in the constructor. The variable d must be smaller or equal to the dimension of the objects, and the product n₁n₂ ^... n_d must equal the number of objects in the array.

Batches can also be determined by an array of doubles α₁, α₂,…, α_d, such that n_i = n^α_i, where n is the number of objects in the array. This way, the condition on the batches is that the sum α₁ + α₂ + ^... + α_d must equal 1.

Constructor Summary

Constructors

Constructor and Description
BatchSort(double[] batchesExponents) Constructs a BatchSort that will use batchesExponents.
BatchSort(int[] batches) Constructs a BatchSort that will use batches.

Method Summary

Methods

Modifier and Type	Method and Description
int	dimension() Returns the greatest dimension used in the sort.
void	sort(double[][] a) Sorts the entire array.
void	sort(double[][] a, int iMin, int iMax) Sorts the subarray of a made of the elements with indices from iMin to iMax-1.
<T extends MultiDimComparable<? super T>> void	sort(T[] a) Sorts the entire array.
<T extends MultiDimComparable<? super T>> void	sort(T[] a, int iMin, int iMax) Sorts the subarray of a made of the elements with indices from iMin to iMax-1.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

BatchSort

public BatchSort(int[] batches)

Constructs a BatchSort that will use batches. The product of elements in batches must equal the size of the arrays to sort; it is verified in sort.

Parameters:

batches - number of batches in each dimension

BatchSort

public BatchSort(double[] batchesExponents)

Constructs a BatchSort that will use batchesExponents. Sum of batchesExponents must equal 1 or an IllegalArgumentException is thrown.

Parameters:

batchesExponents - exponents to compute the batches sizes

Method Detail

sort

public <T extends MultiDimComparable<? super T>> void sort(T[] a,
                                                  int iMin,
                                                  int iMax)

Description copied from interface: MultiDimSort

Sorts the subarray of a made of the elements with indices from iMin to iMax-1.

Specified by:

sort in interface MultiDimSort

Parameters:

a - array to sort

iMin - index of first element to sort

iMax - index of last element to sort is iMax - 1

sort

public <T extends MultiDimComparable<? super T>> void sort(T[] a)

Description copied from interface: MultiDimSort

Sorts the entire array.

Specified by:

sort in interface MultiDimSort

Parameters:

a - array to sort

sort

public void sort(double[][] a,
        int iMin,
        int iMax)

Description copied from interface: MultiDimSort

Sorts the subarray of a made of the elements with indices from iMin to iMax-1.

Specified by:

sort in interface MultiDimSort

Parameters:

a - array to sort

iMin - index of first element to sort

iMax - index of last element to sort is iMax - 1

sort

public void sort(double[][] a)

Description copied from interface: MultiDimSort

Sorts the entire array.

Specified by:

sort in interface MultiDimSort

Parameters:

a - array to sort

dimension

public int dimension()

Description copied from interface: MultiDimSort

Returns the greatest dimension used in the sort.

Specified by:

dimension in interface MultiDimSort

Returns:

greatest dimension used for the sort