com.imsl.stat
Class Sort

java.lang.Object
  com.imsl.stat.Sort

public class Sort
extends Object

A collection of sorting functions.

Class Sort contains ascending and descending methods for sorting elements of an array or a matrix.

The QuickSort algorithm is used, except for short sequences which are handled using an insertion sort.

The QuickSort algorithm is a randomized QuickSort with 3-way partitioning. Basic QucikSort is slow if the sequence to be sorted contains many duplicate keys. The 3-way partitioning algorithm elimiates this problem. The pivot is chosen as the middle element of three potential pivots chosen at random.

The matrix ascending method sorts the rows of real matrix x using a particular row in x as the keys. The sort is algebraic with the first key as the most significant, the second key as the next most significant, etc. When x is sorted in ascending order, the resulting sorted array is such that the following is true:

• For
• For for , then

The observations also can be sorted in descending order.

The rows of x containing the missing value code NaN in at least one of the specified columns are considered as an additional group. These rows are moved to the end of the sorted x.

If all of the sort keys in a pair of rows are equal then the rows keep their original relative order.

The sorting algorithm is based on a quicksort method given by Singleton (1969) with modifications, see Bentley and Sedgewick (1997).

See Also:

Example 1: Array sort with permutation vector, Example 2: Matrix sort containing NaN's

Method Summary

static void	ascending(double[] ra) Sort an array into ascending order.
static void	ascending(double[][] ra, int nKeys) Sort a matrix into ascending order by the first nkeys.
static void	ascending(double[][] ra, int[] indkeys) Sort a matrix into ascending order by specified keys.
static void	ascending(double[][] ra, int[] indkeys, int[] iperm) Sort a matrix into ascending order by specified keys and returns the permutation vector.
static void	ascending(double[][] ra, int nKeys, int[] iperm) Sort an array into ascending order by the first nkeys and returns the permutation vector.
static void	ascending(double[] ra, int[] iperm) Sort an array into ascending order and returns the permutation vector.
static void	ascending(int[] ra) Function to sort an integer array into ascending order.
static void	ascending(int[] ra, int[] iperm) Sort an integer array into ascending order and returns the permutation vector.
static void	descending(double[] ra) Sort an array into descending order.
static void	descending(double[][] ra, int nKeys) Function to sort a matrix into descending order by the first nkeys.
static void	descending(double[][] ra, int[] indkeys) Function to sort a matrix into descending order by specified keys.
static void	descending(double[][] ra, int[] indkeys, int[] iperm) Function to sort a matrix into descending order by specified keys and return the permutation vector.
static void	descending(double[][] ra, int nKeys, int[] iperm) Function to sort an array into descending order by the first nkeys and returns the permutation vector.
static void	descending(double[] ra, int[] iperm) Sort an array into descending order and returns the permutation vector.
static void	descending(int[] ra) Function to sort an integer array into descending order.
static void	descending(int[] ra, int[] iperm) Sort an integer array into descending order and returns the permutation vector.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

ascending

public static void ascending(double[] ra)

Sort an array into ascending order.

Parameters:

ra - double array to be sorted into ascending order

ascending

public static void ascending(double[][] ra,
                             int nKeys)

Sort a matrix into ascending order by the first nkeys.

Parameters:

ra - double matrix to be sorted into ascending order.

nKeys - int containing the first nKeys columns of ra to be used as the sorting keys.

ascending

public static void ascending(double[][] ra,
                             int[] indkeys)

Sort a matrix into ascending order by specified keys.

Parameters:

ra - double matrix to be sorted into ascending order.

indkeys - int array containing the order the columns of ra are to be sorted.

ascending

public static void ascending(double[][] ra,
                             int[] indkeys,
                             int[] iperm)

Sort a matrix into ascending order by specified keys and returns the permutation vector.

Parameters:

ra - double matrix to be sorted into ascending order.

indkeys - int array containing the order the columns of ra are to be sorted. These values must be between 0 and one less than the number of columns in ra.

iperm - int is on input an array the same length as ra. On output, it contains 0, 1, ..., sorted using the same permutations applied to ra.

ascending

public static void ascending(double[][] ra,
                             int nKeys,
                             int[] iperm)

Sort an array into ascending order by the first nkeys and returns the permutation vector.

Parameters:

ra - double array to be sorted into ascending order.

nKeys - int containing the first nKeys columns of ra to be used as the sorting keys.

iperm - int is on input an array the same length as ra. On output, it contains 0, 1, ..., sorted using the same permutations applied to ra.

ascending

public static void ascending(double[] ra,
                             int[] iperm)

Sort an array into ascending order and returns the permutation vector.

Parameters:

ra - double array to be sorted into ascending order

iperm - int is on input an array the same length as ra. On output, it contains 0, 1, ..., sorted using the same permutations applied to ra.

ascending

public static void ascending(int[] ra)

Function to sort an integer array into ascending order.

Parameters:

ra - int array to be sorted into ascending order

ascending

public static void ascending(int[] ra,
                             int[] iperm)

Sort an integer array into ascending order and returns the permutation vector.

Parameters:

ra - int array to be sorted into ascending order

iperm - int is on input an array the same length as ra. On output, it contains 0, 1, ..., sorted using the same permutations applied to ra.

descending

public static void descending(double[] ra)

Sort an array into descending order.

Parameters:

ra - double array to be sorted into descending order

descending

public static void descending(double[][] ra,
                              int nKeys)

Function to sort a matrix into descending order by the first nkeys.

Parameters:

ra - double matrix to be sorted into descending order.

nKeys - int containing the first nKeys columns of ra to be used as the sorting keys.

descending

public static void descending(double[][] ra,
                              int[] indkeys)

Function to sort a matrix into descending order by specified keys.

Parameters:

ra - double matrix to be sorted into descending order.

indkeys - int array containing the order the columns of ra are to be sorted.

descending

public static void descending(double[][] ra,
                              int[] indkeys,
                              int[] iperm)

Function to sort a matrix into descending order by specified keys and return the permutation vector.

Parameters:

ra - double matrix to be sorted into descending order.

indkeys - int array containing the order the columns of ra are to be sorted. These values must be between 0 and one less than the number of columns in ra.

iperm - int array specifying the rearrangement (permutation) of the observations (rows) of ra.

descending

public static void descending(double[][] ra,
                              int nKeys,
                              int[] iperm)

Function to sort an array into descending order by the first nkeys and returns the permutation vector.

Parameters:

ra - double array to be sorted into descending order.

nKeys - int containing the first nKeys columns of ra to be used as the sorting keys.

iperm - int array specifying the rearrangement (permutation) of the observations (rows) of ra.

descending

public static void descending(double[] ra,
                              int[] iperm)

Sort an array into descending order and returns the permutation vector.

Parameters:

ra - double array to be sorted into descending order

iperm - int is on input an array the same length as ra. On output, it contains 0, 1, ..., sorted using the same permutations applied to ra.

descending

public static void descending(int[] ra)

Function to sort an integer array into descending order.

Parameters:

ra - int array to be sorted into descending order

descending

public static void descending(int[] ra,
                              int[] iperm)

Sort an integer array into descending order and returns the permutation vector.

Parameters:

ra - int array to be sorted into descending order

iperm - int is on input an array the same length as ra. On output, it contains 0, 1, ..., sorted using the same permutations applied to ra.