cern.colt.matrix.objectalgo

## Class Sorting

- java.lang.Object
- - cern.colt.PersistentObject
  - - cern.colt.matrix.objectalgo.Sorting

All Implemented Interfaces:
  java.io.Serializable, java.lang.Cloneable

    public class Sorting
    extends PersistentObject

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.

Version:
  1.1, 25/May/2000
See Also:
  `GenericSorting`, `Sorting`, `Arrays`, Serialized Form

### Field Summary

Fields
`static Sorting` `mergeSort` A prefabricated mergesort.
`static Sorting` `quickSort` A prefabricated quicksort.

### Fields inherited from class cern.colt.PersistentObject

`serialVersionUID`

### Method Summary

Methods
`ObjectMatrix1D` `sort(ObjectMatrix1D vector)` Sorts the vector into ascending order, according to the natural ordering.
`ObjectMatrix1D` `sort(ObjectMatrix1D vector, java.util.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

#### quickSort

    public static final Sorting quickSort

A prefabricated quicksort.

#### mergeSort

    public static final Sorting mergeSort

A prefabricated mergesort.

### Method Detail

#### sort

    public ObjectMatrix1D sort(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.

#### sort

    public ObjectMatrix1D sort(ObjectMatrix1D vector,
                      java.util.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.

#### sort

    public 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. 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:
  `java.lang.IndexOutOfBoundsException` - if `column < 0 || column >= matrix.columns()`.

#### sort

    public ObjectMatrix2D sort(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.

#### sort

    public 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. 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

- `A < B iff A.get(row,column) < B.get(row,column)`
- `A == B iff A.get(row,column) == B.get(row,column)`
- `A > B iff A.get(row,column) > B.get(row,column)`

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:
  `java.lang.IndexOutOfBoundsException` - if `row < 0 || row >= matrix.rows() || column < 0 || column >= matrix.columns()`.

#### sort

    public ObjectMatrix3D sort(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.