
Parallel Colt 0.7.2  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 
java.lang.Object cern.colt.PersistentObject cern.colt.matrix.tfloat.algo.FloatSorting
public class FloatSorting
Matrix quicksorts and mergesorts. Use idioms like Sorting.quickSort.sort(...) and Sorting.mergeSort.sort(...) .
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 FormField Summary  

static FloatSorting 
mergeSort
A prefabricated mergesort. 
static FloatSorting 
quickSort
A prefabricated quicksort. 
Fields inherited from class cern.colt.PersistentObject 

serialVersionUID 
Method Summary  

static void 
main(String[] args)

FloatMatrix1D 
sort(FloatMatrix1D vector)
Sorts the vector into ascending order, according to the natural ordering. 
FloatMatrix1D 
sort(FloatMatrix1D vector,
FloatComparator c)
Sorts the vector into ascending order, according to the order induced by the specified comparator. 
FloatMatrix2D 
sort(FloatMatrix2D matrix,
float[] 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. 
FloatMatrix2D 
sort(FloatMatrix2D matrix,
FloatBinFunction1D 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. 
FloatMatrix2D 
sort(FloatMatrix2D matrix,
FloatMatrix1DComparator c)
Sorts the matrix rows according to the order induced by the specified comparator. 
FloatMatrix2D 
sort(FloatMatrix2D matrix,
int column)
Sorts the matrix rows into ascending order, according to the natural ordering of the matrix values in the given column. 
FloatMatrix3D 
sort(FloatMatrix3D matrix,
FloatMatrix2DComparator c)
Sorts the matrix slices according to the order induced by the specified comparator. 
FloatMatrix3D 
sort(FloatMatrix3D 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(FloatMatrix1D vector)
Sorts indexes of the vector into ascending order. 
int[] 
sortIndex(FloatMatrix1D vector,
FloatComparator c)
Sorts indexes of the vector according to the comparator
c . 
int[] 
sortIndex(FloatMatrix1D 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)

Methods inherited from class cern.colt.PersistentObject 

clone 
Methods inherited from class java.lang.Object 

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

public static final FloatSorting quickSort
public static final FloatSorting mergeSort
Method Detail 

public FloatMatrix1D sort(FloatMatrix1D vector)
Example:
7, 1, 3, 1 
==> 1, 1, 3, 7 
vector
 the vector to be sorted.
public int[] sortIndex(FloatMatrix1D vector)
vector
into ascending order.
vector

public int[] sortIndex(FloatMatrix1D vector, IntComparator comp)
vector
according to the comparator comp
.
vector
 comp

public FloatMatrix1D sort(FloatMatrix1D vector, FloatComparator c)
Example:
// sort by sinus of cells FloatComparator comp = new FloatComparator() { public int compare(float a, float b) { float as = Math.sin(a); float 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(FloatMatrix1D vector, FloatComparator c)
vector
according to the comparator
c
.
vector
 c

public FloatMatrix2D sort(FloatMatrix2D matrix, float[] aggregates)
The returned view is backed by this matrix, so changes in the returned view are reflected in this matrix, and viceversa. To sort ranges use subranging 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) FloatMatrix2D matrix = new DenseFloatMatrix2D(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)); float[] aggregates = new float[matrix.rows()]; for (int i = matrix.rows(); i >= 0;) aggregates[i] = matrix.viewRow(i).aggregate(F.plus, F.log); FloatMatrix2D sorted = quickSort(matrix, aggregates); // THE SLOW VERSION (takes some 90 secs) FloatMatrix1DComparator comparator = new FloatMatrix1DComparator() { public int compare(FloatMatrix1D x, FloatMatrix1D y) { float a = x.aggregate(F.plus, F.log); float b = y.aggregate(F.plus, F.log); return a < b ? 1 : a == b ? 0 : 1; } }; FloatMatrix2D 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 FloatMatrix2D sort(FloatMatrix2D 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 FloatMatrix2D sort(FloatMatrix2D matrix, FloatMatrix1DComparator c)
Example:
// sort by sum of values in a row FloatMatrix1DComparator comp = new FloatMatrix1DComparator() { public int compare(FloatMatrix1D a, FloatMatrix1D b) { float as = a.zSum(); float 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 FloatMatrix2D sort(FloatMatrix2D matrix, FloatBinFunction1D aggregate)
The returned view is backed by this matrix, so changes in the returned view are reflected in this matrix, and viceversa. To sort ranges use subranging 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) FloatMatrix2D matrix = new DenseFloatMatrix2D(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) FloatMatrix2D sorted = quickSort(matrix, hep.aida.bin.BinFunctions1D.median); //FloatMatrix2D sorted = quickSort(matrix,hep.aida.bin.BinFunctions1D.sumOfLogarithms); // THE SLOW VERSION (takes some 300 secs) FloatMatrix1DComparator comparator = new FloatMatrix1DComparator() { public int compare(FloatMatrix1D x, FloatMatrix1D y) { float a = cern.colt.matrix.floatalgo.Statistic.bin(x).median(); float b = cern.colt.matrix.floatalgo.Statistic.bin(y).median(); // float a = x.aggregate(F.plus,F.log); // float b = y.aggregate(F.plus,F.log); return a < b ? 1 : a == b ? 0 : 1; } }; FloatMatrix2D sorted = quickSort(matrix, comparator); 
matrix
 the matrix to be sorted.aggregate
 the function to sort on; aggregates values in a row.
public FloatMatrix3D sort(FloatMatrix3D matrix, int row, int column)
The algorithm compares two 2d 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 2d 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 FloatMatrix3D sort(FloatMatrix3D matrix, FloatMatrix2DComparator c)
Example:
// sort by sum of values in a slice FloatMatrix2DComparator comp = new FloatMatrix2DComparator() { public int compare(FloatMatrix2D a, FloatMatrix2D b) { float as = a.zSum(); float 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)

Parallel Colt 0.7.2  
PREV CLASS NEXT CLASS  FRAMES NO FRAMES  
SUMMARY: NESTED  FIELD  CONSTR  METHOD  DETAIL: FIELD  CONSTR  METHOD 