Package org.apache.commons.numbers.arrays

Class Sorting

java.lang.Object

org.apache.commons.numbers.arrays.Sorting

final class Sorting
extends java.lang.Object

Support class for sorting arrays.

Optimal sorting networks are used for small fixed size array sorting.

Note: Requires that the floating-point data contains no NaN values; sorting does not respect the order of signed zeros imposed by Double.compare(double, double).

Since:

1.2

See Also:

Sorting network (Wikipedia), Sorting Networks (Bert Dobbelaere)

Constructor Summary

Constructors

Modifier	Constructor	Description
private	Sorting()	No instances.

Method Summary

Modifier and Type	Method	Description
(package private) static int	insertionSortIndices(int[] x, int n)	Sort the unique indices in-place to the start of the array.
(package private) static void	lowerMedian4(double[] x, int a, int b, int c, int d)	Place the lower median of 4 elements in b; the smaller element in a; and the larger two elements in c, d.
(package private) static void	lowerMedian4(int[] x, int a, int b, int c, int d)	Place the lower median of 4 elements in b; the smaller element in a; and the larger two elements in c, d.
(package private) static void	sort(double[] x, int left, int right)	Sorts an array using an insertion sort.
(package private) static void	sort(int[] x, int left, int right)	Sorts an array using an insertion sort.
(package private) static void	sort3(double[] x, int a, int b, int c)	Sorts the elements at the given distinct indices in an array.
(package private) static void	sort3(int[] x, int a, int b, int c)	Sorts the elements at the given distinct indices in an array.
(package private) static void	sort5(double[] x, int a, int b, int c, int d, int e)	Sorts the elements at the given distinct indices in an array.
(package private) static void	sort5(int[] x, int a, int b, int c, int d, int e)	Sorts the elements at the given distinct indices in an array.
(package private) static int	sortIndices(int[] x, int n)	Sort the unique indices in-place to the start of the array.
(package private) static void	upperMedian4(double[] x, int a, int b, int c, int d)	Place the upper median of 4 elements in c; the smaller two elements in a,b; and the larger element in d.
(package private) static void	upperMedian4(int[] x, int a, int b, int c, int d)	Place the upper median of 4 elements in c; the smaller two elements in a,b; and the larger element in d.

Methods inherited from class java.lang.Object

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

Constructor Detail

Sorting

private Sorting()

No instances.

Method Detail

sort

static void sort(double[] x,
                 int left,
                 int right)

Sorts an array using an insertion sort.

Parameters:

x - Data array.

left - Lower bound (inclusive).

right - Upper bound (inclusive).

sort3

static void sort3(double[] x,
                  int a,
                  int b,
                  int c)

Sorts the elements at the given distinct indices in an array.

Parameters:

x - Data array.

a - Index.

b - Index.

c - Index.

sort5

static void sort5(double[] x,
                  int a,
                  int b,
                  int c,
                  int d,
                  int e)

Sorts the elements at the given distinct indices in an array.

Parameters:

x - Data array.

a - Index.

b - Index.

c - Index.

d - Index.

e - Index.

lowerMedian4

static void lowerMedian4(double[] x,
                         int a,
                         int b,
                         int c,
                         int d)

Place the lower median of 4 elements in b; the smaller element in a; and the larger two elements in c, d.

Parameters:

x - Values

a - Index.

b - Index.

c - Index.

d - Index.

upperMedian4

static void upperMedian4(double[] x,
                         int a,
                         int b,
                         int c,
                         int d)

Place the upper median of 4 elements in c; the smaller two elements in a,b; and the larger element in d.

Parameters:

x - Values

a - Index.

b - Index.

c - Index.

d - Index.

sort

static void sort(int[] x,
                 int left,
                 int right)

Sorts an array using an insertion sort.

Parameters:

x - Data array.

left - Lower bound (inclusive).

right - Upper bound (inclusive).

sort3

static void sort3(int[] x,
                  int a,
                  int b,
                  int c)

Sorts the elements at the given distinct indices in an array.

Parameters:

x - Data array.

a - Index.

b - Index.

c - Index.

sort5

static void sort5(int[] x,
                  int a,
                  int b,
                  int c,
                  int d,
                  int e)

Sorts the elements at the given distinct indices in an array.

Parameters:

x - Data array.

a - Index.

b - Index.

c - Index.

d - Index.

e - Index.

lowerMedian4

static void lowerMedian4(int[] x,
                         int a,
                         int b,
                         int c,
                         int d)

Place the lower median of 4 elements in b; the smaller element in a; and the larger two elements in c, d.

Parameters:

x - Values

a - Index.

b - Index.

c - Index.

d - Index.

upperMedian4

static void upperMedian4(int[] x,
                         int a,
                         int b,
                         int c,
                         int d)

Place the upper median of 4 elements in c; the smaller two elements in a,b; and the larger element in d.

Parameters:

x - Values

a - Index.

b - Index.

c - Index.

d - Index.

insertionSortIndices

static int insertionSortIndices(int[] x,
                                int n)

Sort the unique indices in-place to the start of the array. The number of unique indices is returned.

Uses an insertion sort modified to ignore duplicates. Use on small n.

Warning: Requires n > 0. The array contents after the count of unique indices c are unchanged (i.e. [c, n). This may change the count of each unique index in the entire array.

Parameters:

x - Indices.

n - Number of indices.

Returns:

the number of unique indices

sortIndices

static int sortIndices(int[] x,
                       int n)

Sort the unique indices in-place to the start of the array. The number of unique indices is returned.

Uses an Order(1) data structure to ignore duplicates.

Warning: Requires n > 0. The array contents after the count of unique indices c are unchanged (i.e. [c, n). This may change the count of each unique index in the entire array.

Parameters:

x - Indices.

n - Number of indices.

Returns:

the number of unique indices