
Colt 1.2.0  
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.objectalgo.Sorting
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 Sorting 
mergeSort
A prefabricated mergesort. 
static Sorting 
quickSort
A prefabricated quicksort. 
Fields inherited from class cern.colt.PersistentObject 
serialVersionUID 
Method Summary  
ObjectMatrix1D 
sort(ObjectMatrix1D vector)
Sorts the vector into ascending order, according to the natural ordering. 
ObjectMatrix1D 
sort(ObjectMatrix1D vector,
Comparator c)
Sorts the vector into ascending order, according to the order induced by the specified comparator. 
ObjectMatrix2D 
sort(ObjectMatrix2D matrix,
int column)
Sorts the matrix rows into ascending order, according to the natural ordering of the matrix values in the given column. 
ObjectMatrix2D 
sort(ObjectMatrix2D matrix,
ObjectMatrix1DComparator c)
Sorts the matrix rows according to the order induced by the specified comparator. 
ObjectMatrix3D 
sort(ObjectMatrix3D 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. 
ObjectMatrix3D 
sort(ObjectMatrix3D matrix,
ObjectMatrix2DComparator c)
Sorts the matrix slices according to the order induced by the specified comparator. 
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 Sorting quickSort
public static final Sorting mergeSort
Method Detail 
public ObjectMatrix1D sort(ObjectMatrix1D vector)
Example:
7, 1, 3, 1 
==> 1, 1, 3, 7 
vector
 the vector to be sorted.
public ObjectMatrix1D sort(ObjectMatrix1D vector, Comparator c)
Example:
// sort by sinus of cells ObjectComparator comp = new ObjectComparator() { public int compare(Object a, Object b) { Object as = Math.sin(a); Object 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 ObjectMatrix2D sort(ObjectMatrix2D 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 ObjectMatrix2D sort(ObjectMatrix2D matrix, ObjectMatrix1DComparator c)
Example:
// sort by sum of values in a row ObjectMatrix1DComparator comp = new ObjectMatrix1DComparator() { public int compare(ObjectMatrix1D a, ObjectMatrix1D b) { Object as = a.zSum(); Object 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 ObjectMatrix3D sort(ObjectMatrix3D 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 ObjectMatrix3D sort(ObjectMatrix3D matrix, ObjectMatrix2DComparator c)
Example:
// sort by sum of values in a slice ObjectMatrix2DComparator comp = new ObjectMatrix2DComparator() { public int compare(ObjectMatrix2D a, ObjectMatrix2D b) { Object as = a.zSum(); Object 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.

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