public class DoubleSorting extends PersistentObject
This is another case demonstrating one primary goal of this library: Delivering easy to use, yet very efficient APIs. The sorts return convenient sort views. This enables the usage of algorithms which scale well with the problem size: For example, sorting a 1000000 x 10000 or a 1000000 x 100 x 100 matrix performs just as fast as sorting a 1000000 x 1 matrix. This is so, because internally the algorithms only move around integer indexes, they do not physically move around entire rows or slices. The original matrix is left unaffected.
The quicksort is a derivative of the JDK 1.2 V1.26 algorithms (which are, in turn, based on Bentley's and McIlroy's fine work). The mergesort is a derivative of the JAL algorithms, with optimisations taken from the JDK algorithms. Mergesort is stable (by definition), while quicksort is not. A stable sort is, for example, helpful, if matrices are sorted successively by multiple columns. It preserves the relative position of equal elements.
GenericSorting,
Sorting,
Arrays,
Serialized Form| Modifier and Type | Field and Description |
|---|---|
static DoubleSorting |
mergeSort
A prefabricated mergesort.
|
static DoubleSorting |
quickSort
A prefabricated quicksort.
|
| Modifier and Type | Method and Description |
|---|---|
static void |
main(String[] args) |
DoubleMatrix1D |
sort(DoubleMatrix1D vector)
Sorts the vector into ascending order, according to the natural
ordering.
|
DoubleMatrix1D |
sort(DoubleMatrix1D vector,
DoubleComparator c)
Sorts the vector into ascending order, according to the order induced by
the specified comparator.
|
DoubleMatrix2D |
sort(DoubleMatrix2D matrix,
double[] aggregates)
Sorts the matrix rows into ascending order, according to the natural
ordering of the matrix values in the virtual column
aggregates; Particularly efficient when comparing expensive
aggregates, because aggregates need not be recomputed time and again, as
is the case for comparator based sorts.
|
DoubleMatrix2D |
sort(DoubleMatrix2D matrix,
DoubleBinFunction1D aggregate)
Sorts the matrix rows into ascending order, according to the natural
ordering of the values computed by applying the given aggregation
function to each row; Particularly efficient when comparing expensive
aggregates, because aggregates need not be recomputed time and again, as
is the case for comparator based sorts.
|
DoubleMatrix2D |
sort(DoubleMatrix2D matrix,
DoubleMatrix1DComparator c)
Sorts the matrix rows according to the order induced by the specified
comparator.
|
DoubleMatrix2D |
sort(DoubleMatrix2D matrix,
int column)
Sorts the matrix rows into ascending order, according to the natural
ordering of the matrix values in the given column.
|
DoubleMatrix3D |
sort(DoubleMatrix3D matrix,
DoubleMatrix2DComparator c)
Sorts the matrix slices according to the order induced by the specified
comparator.
|
DoubleMatrix3D |
sort(DoubleMatrix3D matrix,
int row,
int column)
Sorts the matrix slices into ascending order, according to the natural
ordering of the matrix values in the given [row,column]
position.
|
int[] |
sortIndex(DoubleMatrix1D vector)
Sorts indexes of the
vector into ascending order. |
int[] |
sortIndex(DoubleMatrix1D vector,
DoubleComparator c)
Sorts indexes of the
vector according to the comparator
c. |
int[] |
sortIndex(DoubleMatrix1D vector,
IntComparator comp)
Multithreaded method that sorts indexes of the
vector
according to the comparator comp. |
static void |
zdemo1()
Demonstrates advanced sorting.
|
static void |
zdemo2()
Demonstrates advanced sorting.
|
static void |
zdemo3()
Demonstrates advanced sorting.
|
static void |
zdemo5(int rows,
int columns,
boolean print)
Demonstrates sorting with precomputation of aggregates (median and sum of
logarithms).
|
static void |
zdemo6()
Demonstrates advanced sorting.
|
static void |
zdemo7(int rows,
int columns,
boolean print)
Demonstrates sorting with precomputation of aggregates, comparing
mergesort with quicksort.
|
static void |
zdemo8(int size) |
clonepublic static final DoubleSorting quickSort
public static final DoubleSorting mergeSort
public DoubleMatrix1D sort(DoubleMatrix1D vector)
Example:
| 7, 1, 3, 1 |
==> 1, 1, 3, 7 |
vector - the vector to be sorted.public int[] sortIndex(DoubleMatrix1D vector)
vector into ascending order.vector - public int[] sortIndex(DoubleMatrix1D vector, IntComparator comp)
vector
according to the comparator comp.vector - comp - public DoubleMatrix1D sort(DoubleMatrix1D vector, DoubleComparator c)
Example:
// sort by sinus of cells
DoubleComparator comp = new DoubleComparator() {
public int compare(double a, double b) {
double as = Math.sin(a);
double bs = Math.sin(b);
return as < bs ? -1 : as == bs ? 0 : 1;
}
};
sorted = quickSort(vector, comp);
vector - the vector to be sorted.c - the comparator to determine the order.public int[] sortIndex(DoubleMatrix1D vector, DoubleComparator c)
vector according to the comparator
c.vector - c - public DoubleMatrix2D sort(DoubleMatrix2D matrix, double[] aggregates)
The returned view is backed by this matrix, so changes in the returned view are reflected in this matrix, and vice-versa. To sort ranges use sub-ranging views. To sort columns by rows, use dice views. To sort descending, use flip views ...
Example: Each aggregate is the sum of a row
| 4 x 2 matrix: 1, 1 5, 4 3, 0 4, 4 |
aggregates= 2 9 3 8 ==> |
4 x 2 matrix: |
// sort 10000 x 1000 matrix by sum of logarithms in a row (i.e. by geometric mean)
DoubleMatrix2D matrix = new DenseDoubleMatrix2D(10000, 1000);
matrix.assign(new cern.jet.random.engine.MersenneTwister()); // initialized randomly
cern.jet.math.Functions F = cern.jet.math.Functions.functions; // alias for convenience
// THE QUICK VERSION (takes some 3 secs)
// aggregates[i] = Sum(log(row));
double[] aggregates = new double[matrix.rows()];
for (int i = matrix.rows(); --i >= 0;)
aggregates[i] = matrix.viewRow(i).aggregate(F.plus, F.log);
DoubleMatrix2D sorted = quickSort(matrix, aggregates);
// THE SLOW VERSION (takes some 90 secs)
DoubleMatrix1DComparator comparator = new DoubleMatrix1DComparator() {
public int compare(DoubleMatrix1D x, DoubleMatrix1D y) {
double a = x.aggregate(F.plus, F.log);
double b = y.aggregate(F.plus, F.log);
return a < b ? -1 : a == b ? 0 : 1;
}
};
DoubleMatrix2D sorted = quickSort(matrix, comparator);
|
matrix - the matrix to be sorted.aggregates - the values to sort on. (As a side effect, this array will also
get sorted).IndexOutOfBoundsException - if aggregates.length != matrix.rows().public DoubleMatrix2D sort(DoubleMatrix2D matrix, int column)
Example:
| 4 x 2 matrix: 7, 6 5, 4 3, 2 1, 0 |
column = 0; |
4 x 2 matrix: |
matrix - the matrix to be sorted.column - the index of the column inducing the order.IndexOutOfBoundsException - if column < 0 || column >= matrix.columns().public DoubleMatrix2D sort(DoubleMatrix2D matrix, DoubleMatrix1DComparator c)
Example:
// sort by sum of values in a row
DoubleMatrix1DComparator comp = new DoubleMatrix1DComparator() {
public int compare(DoubleMatrix1D a, DoubleMatrix1D b) {
double as = a.zSum();
double bs = b.zSum();
return as < bs ? -1 : as == bs ? 0 : 1;
}
};
sorted = quickSort(matrix, comp);
matrix - the matrix to be sorted.c - the comparator to determine the order.public DoubleMatrix2D sort(DoubleMatrix2D matrix, DoubleBinFunction1D aggregate)
The returned view is backed by this matrix, so changes in the returned view are reflected in this matrix, and vice-versa. To sort ranges use sub-ranging views. To sort columns by rows, use dice views. To sort descending, use flip views ...
Example: Each aggregate is the sum of a row
| 4 x 2 matrix: 1, 1 5, 4 3, 0 4, 4 |
aggregates= hep.aida.bin.BinFunctions1D.sum ==> |
4 x 2 matrix: |
// sort 10000 x 1000 matrix by median or by sum of logarithms in a row (i.e. by geometric mean)
DoubleMatrix2D matrix = new DenseDoubleMatrix2D(10000, 1000);
matrix.assign(new cern.jet.random.engine.MersenneTwister()); // initialized randomly
cern.jet.math.Functions F = cern.jet.math.Functions.functions; // alias for convenience
// THE QUICK VERSION (takes some 10 secs)
DoubleMatrix2D sorted = quickSort(matrix, hep.aida.bin.BinFunctions1D.median);
//DoubleMatrix2D sorted = quickSort(matrix,hep.aida.bin.BinFunctions1D.sumOfLogarithms);
// THE SLOW VERSION (takes some 300 secs)
DoubleMatrix1DComparator comparator = new DoubleMatrix1DComparator() {
public int compare(DoubleMatrix1D x, DoubleMatrix1D y) {
double a = cern.colt.matrix.doublealgo.Statistic.bin(x).median();
double b = cern.colt.matrix.doublealgo.Statistic.bin(y).median();
// double a = x.aggregate(F.plus,F.log);
// double b = y.aggregate(F.plus,F.log);
return a < b ? -1 : a == b ? 0 : 1;
}
};
DoubleMatrix2D sorted = quickSort(matrix, comparator);
|
matrix - the matrix to be sorted.aggregate - the function to sort on; aggregates values in a row.public DoubleMatrix3D sort(DoubleMatrix3D matrix, int row, int column)
The algorithm compares two 2-d slices at a time, determinining whether one is smaller, equal or larger than the other. Comparison is based on the cell [row,column] within a slice. Let A and B be two 2-d slices. Then we have the following rules
matrix - the matrix to be sorted.row - the index of the row inducing the order.column - the index of the column inducing the order.IndexOutOfBoundsException - if
row < 0 || row >= matrix.rows() || column < 0 || column >= matrix.columns()
.public DoubleMatrix3D sort(DoubleMatrix3D matrix, DoubleMatrix2DComparator c)
Example:
// sort by sum of values in a slice
DoubleMatrix2DComparator comp = new DoubleMatrix2DComparator() {
public int compare(DoubleMatrix2D a, DoubleMatrix2D b) {
double as = a.zSum();
double bs = b.zSum();
return as < bs ? -1 : as == bs ? 0 : 1;
}
};
sorted = quickSort(matrix, comp);
matrix - the matrix to be sorted.c - the comparator to determine the order.public static void zdemo1()
public static void zdemo2()
public static void zdemo3()
public static void zdemo5(int rows,
int columns,
boolean print)
public static void zdemo6()
public static void zdemo7(int rows,
int columns,
boolean print)
public static void zdemo8(int size)
public static void main(String[] args)
Jump to the Parallel Colt Homepage