public class Arrays
extends java.lang.Object
In addition to commodity methods, this class contains Swapper
-based implementations
of quicksort and of
a stable, in-place mergesort. These
generic sorting methods can be used to sort any kind of list, but they find their natural
usage, for instance, in sorting arrays in parallel.
Some algorithms provide a parallel version that will by default use the
common pool, but this can be overridden by calling the
function in a task already in the ForkJoinPool
that the operation should run in. For example,
something along the lines of "poolToParallelSortIn.invoke(() -> parallelQuickSort(arrayToSort))
"
will run the parallel sort in poolToParallelSortIn
instead of the default pool.
Arrays
Modifier and Type | Field and Description |
---|---|
static int |
MAX_ARRAY_SIZE
This is a safe value used by
ArrayList (as of Java 7) to avoid
throwing OutOfMemoryError on some JVMs. |
Modifier and Type | Method and Description |
---|---|
static void |
ensureFromTo(int arrayLength,
int from,
int to)
Ensures that a range given by its first (inclusive) and last (exclusive) elements fits an
array of given length.
|
static void |
ensureOffsetLength(int arrayLength,
int offset,
int length)
Ensures that a range given by an offset and a length fits an array of given length.
|
static void |
mergeSort(int from,
int to,
IntComparator c,
Swapper swapper)
Sorts the specified range of elements using the specified swapper and according to the order induced by the specified
comparator using mergesort.
|
static void |
parallelQuickSort(int from,
int to,
IntComparator comp,
Swapper swapper)
Sorts the specified range of elements using the specified swapper and according to the order induced by the specified
comparator using a parallel quicksort.
|
static void |
quickSort(int from,
int to,
IntComparator comp,
Swapper swapper)
Sorts the specified range of elements using the specified swapper and according to the order induced by the specified
comparator using parallel quicksort.
|
public static final int MAX_ARRAY_SIZE
ArrayList
(as of Java 7) to avoid
throwing OutOfMemoryError
on some JVMs. We adopt the same value.public static void ensureFromTo(int arrayLength, int from, int to)
This method may be used whenever an array range check is needed.
In Java 9 and up, this method should be considered deprecated in favor of the
java.util.Objects#checkFromToIndex(int, int, int)
method, which may be intrinsified
in recent JVMs.
arrayLength
- an array length.from
- a start index (inclusive).to
- an end index (inclusive).java.lang.IllegalArgumentException
- if from
is greater than to
.java.lang.ArrayIndexOutOfBoundsException
- if from
or to
are greater than
arrayLength
or negative.public static void ensureOffsetLength(int arrayLength, int offset, int length)
This method may be used whenever an array range check is needed.
In Java 9 and up, this method should be considered deprecated in favor of the
java.util.Objects#checkFromIndexSize(int, int, int)
method, which may be intrinsified
in recent JVMs.
arrayLength
- an array length.offset
- a start index for the fragmentlength
- a length (the number of elements in the fragment).java.lang.IllegalArgumentException
- if length
is negative.java.lang.ArrayIndexOutOfBoundsException
- if offset
is negative or
offset
+length
is greater than arrayLength
.public static void mergeSort(int from, int to, IntComparator c, Swapper swapper)
This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort. The sorting algorithm is an in-place mergesort that is significantly slower than a standard mergesort, as its running time is O(n (log n)2), but it does not allocate additional memory; as a result, it can be used as a generic sorting algorithm.
from
- the index of the first element (inclusive) to be sorted.to
- the index of the last element (exclusive) to be sorted.c
- the comparator to determine the order of the generic data (arguments are positions).swapper
- an object that knows how to swap the elements at any two positions.public static void parallelQuickSort(int from, int to, IntComparator comp, Swapper swapper)
The sorting algorithm is a tuned quicksort adapted from Jon L. Bentley and M. Douglas McIlroy, “Engineering a Sort Function”, Software: Practice and Experience, 23(11), pages 1249−1265, 1993.
from
- the index of the first element (inclusive) to be sorted.to
- the index of the last element (exclusive) to be sorted.comp
- the comparator to determine the order of the generic data.swapper
- an object that knows how to swap the elements at any two positions.public static void quickSort(int from, int to, IntComparator comp, Swapper swapper)
The sorting algorithm is a tuned quicksort adapted from Jon L. Bentley and M. Douglas McIlroy, “Engineering a Sort Function”, Software: Practice and Experience, 23(11), pages 1249−1265, 1993.
from
- the index of the first element (inclusive) to be sorted.to
- the index of the last element (exclusive) to be sorted.comp
- the comparator to determine the order of the generic data.swapper
- an object that knows how to swap the elements at any two positions.