Colt 1.0.1

cern.colt.matrix.objectalgo
Class Sorting

java.lang.Object
  |
  +--cern.colt.matrix.objectalgo.Sorting

public class Sorting
extends Object

Matrix Quicksorts. Come in two variants: a) Sorting according to the order induces by a user supplied comparator, b) sorting according to natural ordering. Natural ordering means cells must implement {@java.lang.Comparable}. In both variants, cells must not be null. All sorting algorithms are tuned quicksorts, adapted from Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993). This algorithm offers n*log(n) performance on many data sets that cause other quicksorts to degrade to quadratic performance.

See Also:
Sorting, GenericSorting, java.util.Arrays

Method Summary
static ObjectMatrix1D quickSort(ObjectMatrix1D vector)
          Sorts the vector into ascending order, according to the natural ordering.
static ObjectMatrix1D quickSort(ObjectMatrix1D vector, Comparator c)
          Sorts the vector into ascending order, according to the order induced by the specified comparator.
static ObjectMatrix2D quickSort(ObjectMatrix2D matrix, int column)
          Sorts the matrix rows into ascending order, according to the natural ordering of the matrix values in the given column.
static ObjectMatrix2D quickSort(ObjectMatrix2D matrix, ObjectMatrix1DComparator c)
          Sorts the matrix rows according to the order induced by the specified comparator.
static ObjectMatrix3D quickSort(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.
static ObjectMatrix3D quickSort(ObjectMatrix3D matrix, ObjectMatrix2DComparator c)
          Sorts the matrix slices according to the order induced by the specified comparator.
 
Methods inherited from class java.lang.Object
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Method Detail

quickSort

public static ObjectMatrix1D quickSort(ObjectMatrix1D vector)
Sorts the vector into ascending order, according to the natural ordering. 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 descending, use flip views ...

Example:
7, 1, 3, 1

==> 1, 1, 3, 7
The vector IS NOT SORTED.
The new VIEW IS SORTED.

Parameters:
vector - the vector to be sorted.
Returns:
a new sorted vector (matrix) view. Note that the original matrix is left unaffected.

quickSort

public static ObjectMatrix1D quickSort(ObjectMatrix1D vector,
                                       Comparator c)
Sorts the vector into ascending order, according to the order induced by the specified comparator. The returned view is backed by this matrix, so changes in the returned view are reflected in this matrix, and vice-versa. The algorithm compares two cells at a time, determinining whether one is smaller, equal or larger than the other. To sort ranges use sub-ranging views. To sort descending, use flip views ...

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);
Parameters:
vector - the vector to be sorted.
c - the comparator to determine the order.
Returns:
a new matrix view sorted as specified. Note that the original vector (matrix) is left unaffected.

quickSort

public static ObjectMatrix2D quickSort(ObjectMatrix2D matrix,
                                       int column)
Sorts the matrix rows into ascending order, according to the natural ordering of the matrix values in the given column. 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:
4 x 2 matrix:
7, 6
5, 4
3, 2
1, 0

column = 0;
view = quickSort(matrix,column);
System.out.println(view);

==>

4 x 2 matrix:
1, 0
3, 2
5, 4
7, 6

The matrix IS NOT SORTED.
The new VIEW IS SORTED.

Parameters:
matrix - the matrix to be sorted.
column - the index of the column inducing the order.
Returns:
a new matrix view having rows sorted by the given column. Note that the original matrix is left unaffected.
Throws:
IndexOutOfBoundsException - if column < 0 || column >= matrix.columns().

quickSort

public static ObjectMatrix2D quickSort(ObjectMatrix2D matrix,
                                       ObjectMatrix1DComparator c)
Sorts the matrix rows according to the order induced by the specified comparator. The returned view is backed by this matrix, so changes in the returned view are reflected in this matrix, and vice-versa. The algorithm compares two rows (1-d matrices) at a time, determinining whether one is smaller, equal or larger than the other. To sort ranges use sub-ranging views. To sort columns by rows, use dice views. To sort descending, use flip views ...

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);
Parameters:
matrix - the matrix to be sorted.
c - the comparator to determine the order.
Returns:
a new matrix view having rows sorted as specified. Note that the original matrix is left unaffected.

quickSort

public static ObjectMatrix3D quickSort(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. 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 by other dimensions, use dice views. To sort descending, use flip views ...

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

Parameters:
matrix - the matrix to be sorted.
row - the index of the row inducing the order.
column - the index of the column inducing the order.
Returns:
a new matrix view having slices sorted by the values of the slice view matrix.viewRow(row).viewColumn(column). Note that the original matrix is left unaffected.
Throws:
IndexOutOfBoundsException - if row < 0 || row >= matrix.rows() || column < 0 || column >= matrix.columns().

quickSort

public static ObjectMatrix3D quickSort(ObjectMatrix3D matrix,
                                       ObjectMatrix2DComparator c)
Sorts the matrix slices according to the order induced by the specified comparator. The returned view is backed by this matrix, so changes in the returned view are reflected in this matrix, and vice-versa. The algorithm compares two slices (2-d matrices) at a time, determinining whether one is smaller, equal or larger than the other. To sort ranges use sub-ranging views. To sort by other dimensions, use dice views. To sort descending, use flip views ...

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);
Parameters:
matrix - the matrix to be sorted.
c - the comparator to determine the order.
Returns:
a new matrix view having slices sorted as specified. Note that the original matrix is left unaffected.

Colt 1.0.1

Submit a bug or feature. Check the Colt home page for the latest news.