## Class FloatSorting

- java.lang.Object
- cern.colt.PersistentObject
- cern.colt.matrix.tfloat.algo.FloatSorting

- All Implemented Interfaces:
- Serializable, Cloneable

public class FloatSortingextends 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.- See Also:
`GenericSorting`

,`Sorting`

,`Arrays`

, Serialized Form

### Field Summary

Fields Modifier and Type Field and Description `static FloatSorting`

**mergeSort**A prefabricated mergesort.`static FloatSorting`

**quickSort**A prefabricated quicksort.

### Method Summary

Methods Modifier and Type Method and Description `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`

### Field Detail

#### quickSort

public static final FloatSorting quickSort

A prefabricated quicksort.

#### mergeSort

public static final FloatSorting mergeSort

A prefabricated mergesort.

### Method Detail

#### sort

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

#### sortIndex

public int[] sortIndex(FloatMatrix1D vector)

Sorts indexes of the`vector`

into ascending order.- Parameters:
`vector`

-- Returns:
- sorted indexes

#### sortIndex

public int[] sortIndex(FloatMatrix1D vector, IntComparator comp)

Multithreaded method that sorts indexes of the`vector`

according to the comparator`comp`

.- Parameters:
`vector`

-`comp`

-- Returns:
- sorted indexes

#### sort

public FloatMatrix1D sort(FloatMatrix1D vector, FloatComparator 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 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);

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

#### sortIndex

public int[] sortIndex(FloatMatrix1D vector, FloatComparator c)

Sorts indexes of the`vector`

according to the comparator`c`

.- Parameters:
`vector`

-`c`

-- Returns:
- sorted indexes

#### sort

public 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. Essentially, this algorithm makes expensive comparisons cheap. Normally each element of`aggregates`is a summary measure of a row. Speedup over comparator based sorting =`2*log(rows)`, on average. For this operation, quicksort is usually faster.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:`

1, 1

3, 0

4, 4

5, 4

The matrix IS NOT SORTED.

The new VIEW IS SORTED.// 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);

- Parameters:
`matrix`

- the matrix to be sorted.`aggregates`

- the values to sort on. (As a side effect, this array will also get sorted).- Returns:
- a new matrix view having rows sorted.
**Note that the original matrix is left unaffected.** - Throws:
`IndexOutOfBoundsException`

- if`aggregates.length != matrix.rows()`.

#### sort

public 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. 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()`.

#### sort

public FloatMatrix2D sort(FloatMatrix2D matrix, FloatMatrix1DComparator 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 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);

- 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 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. Essentially, this algorithm makes expensive comparisons cheap. Normally`aggregates`defines a summary measure of a row. Speedup over comparator based sorting =`2*log(rows)`, on average.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:`

1, 1

3, 0

4, 4

5, 4

The matrix IS NOT SORTED.

The new VIEW IS SORTED.// 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);

- Parameters:
`matrix`

- the matrix to be sorted.`aggregate`

- the function to sort on; aggregates values in a row.- Returns:
- a new matrix view having rows sorted.
**Note that the original matrix is left unaffected.**

#### sort

public 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. 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:
`IndexOutOfBoundsException`

- if`row < 0 || row >= matrix.rows() || column < 0 || column >= matrix.columns()`.

#### sort

public FloatMatrix3D sort(FloatMatrix3D matrix, FloatMatrix2DComparator 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 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);

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

#### zdemo1

public static void zdemo1()

Demonstrates advanced sorting. Sorts by sum of row.

#### zdemo2

public static void zdemo2()

Demonstrates advanced sorting. Sorts by sum of slice.

#### zdemo3

public static void zdemo3()

Demonstrates advanced sorting. Sorts by sinus of cell values.

#### zdemo5

public static void zdemo5(int rows, int columns, boolean print)

Demonstrates sorting with precomputation of aggregates (median and sum of logarithms).

#### zdemo6

public static void zdemo6()

Demonstrates advanced sorting. Sorts by sum of row.

#### zdemo7

public static void zdemo7(int rows, int columns, boolean print)

Demonstrates sorting with precomputation of aggregates, comparing mergesort with quicksort.

#### zdemo8

public static void zdemo8(int size)

#### main

public static void main(String[] args)

**SCaVis 1.8 © jWork.org**