|
SSJ V. labo. |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectumontreal.iro.lecuyer.util.HilbertCurveSplitSort
public class HilbertCurveSplitSort
HilbertCurveSplitSort
This sort sort is similar to SplitSort, except that when applying the split sort, the elements are also mapped to the d-dimensional unit hypercube [0, 1)d as explained below, and then re-ordered by following a Hilbert curve. During the split sort, the entire space is actually split into n rectangular boxes, with exactly one point per box. Each box is given a d-dimensional number (or label), as follows, where each coordinate is represented by a binary string. At first, each string is empty. Then, each time a box is split in two according to coordinate j, we add a 0 on the right of the string of coordinate j for the lower box and a 1 for the upper box. At the end, we interpret these strings as fractional binary expansions of new coordinates in [0, 1)d. That is, this labeling maps the points to the unit hypercube. After this labeling, we sort the points exactly as in HilbertCurveSort.
The implementation notes in HilbertCurveBatchSort also apply here.
Constructor Summary | |
---|---|
HilbertCurveSplitSort(int d)
. |
Method Summary | ||
---|---|---|
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. |
|
|
sort(T[] a)
Sorts the entire array. |
|
|
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 |
---|
public HilbertCurveSplitSort(int d)
Method Detail |
---|
public <T extends MultiDimComparable<? super T>> void sort(T[] a, int iMin, int iMax)
MultiDimSort
sort
in interface MultiDimSort
a
- array to sortiMin
- index of first element to sortiMax
- index of last element to sort is
public <T extends MultiDimComparable<? super T>> void sort(T[] a)
MultiDimSort
sort
in interface MultiDimSort
a
- array to sortpublic void sort(double[][] a, int iMin, int iMax)
MultiDimSort
sort
in interface MultiDimSort
a
- array to sortiMin
- index of first element to sortiMax
- index of last element to sort is
public void sort(double[][] a)
MultiDimSort
sort
in interface MultiDimSort
a
- array to sortpublic int dimension()
MultiDimSort
dimension
in interface MultiDimSort
|
SSJ V. labo. |
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |