|
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 MultiDimSorta - 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 MultiDimSorta - array to sort
public void sort(double[][] a,
int iMin,
int iMax)
MultiDimSort
sort in interface MultiDimSorta - 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 MultiDimSorta - 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 | ||||||||