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
All Methods Static Methods Concrete Methods 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 inb
; the smaller element ina
; and the larger two elements inc, d
.(package private) static void
lowerMedian4(int[] x, int a, int b, int c, int d)
Place the lower median of 4 elements inb
; the smaller element ina
; and the larger two elements inc, 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 inc
; the smaller two elements ina,b
; and the larger element ind
.(package private) static void
upperMedian4(int[] x, int a, int b, int c, int d)
Place the upper median of 4 elements inc
; the smaller two elements ina,b
; and the larger element ind
.
-
-
-
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 inb
; the smaller element ina
; and the larger two elements inc, d
.- Parameters:
x
- Valuesa
- 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 inc
; the smaller two elements ina,b
; and the larger element ind
.- Parameters:
x
- Valuesa
- 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 inb
; the smaller element ina
; and the larger two elements inc, d
.- Parameters:
x
- Valuesa
- 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 inc
; the smaller two elements ina,b
; and the larger element ind
.- Parameters:
x
- Valuesa
- 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 indicesc
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 indicesc
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
-
-