|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectpapaya.Sorting
public final class Sorting
Class for getting the array of indices that can be used to sort the array in ascending or descending order. This is especially useful if you want to preserve the ordering of your original array, or if you want to manipulate more than one array according to the sorted order of only one of them.
For example, assume we have three arrays X, Y and Z. We want to sort all three arrays by
X (or some arbitrary comparison function). For example, we have
X={3, 2, 1}, Y={3.0, 1.0, 2.0}, Z={6.0, 7.0, 8.0}
. The output should
be
.
To do this, we can use the indices corresponding to the elements of
X={1, 2, 3}, Y={2.0, 1.0, 3.0}, Z={8.0, 7.0, 6.0}X
sorted
in ascending order:
X={3,2,1}
so indicesForSorting = {2,1,0}
(X[2]
holds the smallest value of X
,
X[1]
holds the next smallest value of X
, and X[0]
holds the largest value of X
).
The indicesForSorting
can then be used to arrange Y
and Z
in the same order.
The algorithm used to obtain these indices is a modified version of the tuned quicksort proposed by Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993) (program 7 of the paper; currently used in the Arrays.sort() method to sort arrays).
It is a modified version in the sense that the original array remains unsorted. Instead, a copy of the original array is used in the sorting routine, and the array of indices [0,1,2,...N-1] sorted concurrently with the array being sorted.
Method Summary | |
---|---|
static int[] |
indices(double[] a,
boolean isAscending)
|
static int[] |
indices(double[] a,
int fromIndex,
int toIndex,
boolean isAscending)
|
static int[] |
indices(float[] a,
boolean isAscending)
Gets the array of indices that can be used to sort the array in ascending or descending order. |
static int[] |
indices(float[] a,
int fromIndex,
int toIndex,
boolean isAscending)
Gets the array of indices that can be used to sort the section of the input array going from fromIndex (inclusive) to toIndex (exclusive)
in ascending or descending order. |
static int[] |
indices(int[] a,
boolean isAscending)
|
static int[] |
indices(int[] a,
int fromIndex,
int toIndex,
boolean isAscending)
|
static void |
twoArrays(double[] x,
double[] y,
int fromIndex,
int toIndex,
boolean isAscending)
|
static void |
twoArrays(float[] x,
float[] y,
int fromIndex,
int toIndex,
boolean isAscending)
Sorts the input x and y arrays according to
x and going from fromIndex (inclusive) to toIndex (exclusive)
in ascending or descending order. |
static void |
twoArrays(int[] x,
int[] y,
int fromIndex,
int toIndex,
boolean isAscending)
|
Methods inherited from class java.lang.Object |
---|
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Method Detail |
---|
public static int[] indices(float[] a, boolean isAscending)
The algorithm used to obtain these indices is a modified version of the tuned quicksort proposed by Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993) (program 7 of the paper; currently used in the Arrays.sort() method to sort arrays).
It is a modified version in the sense that the original array remains unsorted. Instead, a copy of the original array is used in the sorting routine, and the array of indices [0,1,2,...N-1] sorted concurrently with the array being sorted.
a
- the input arrayisAscending
- true for data sorted in increasing order.
fromIndex > toIndex
ArrayIndexOutOfBoundsException
- if fromIndex < 0
or
toIndex > a.length
public static int[] indices(double[] a, boolean isAscending)
public static int[] indices(int[] a, boolean isAscending)
public static int[] indices(float[] a, int fromIndex, int toIndex, boolean isAscending)
fromIndex
(inclusive) to toIndex
(exclusive)
in ascending or descending order.
The algorithm used to obtain these indices is a modified version of the tuned quicksort proposed by Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993) (program 7 of the paper; currently used in the Arrays.sort() method to sort arrays).
It is a modified version in the sense that the original array remains unsorted. Instead, a copy of the original array is used in the sorting routine, and the array of indices [fromIndex,fromIndex+1, ... , toIndex-1] sorted concurrently with the array being sorted.
a
- the array to be sorted.fromIndex
- the index of the first element (inclusive) to be
sorted.toIndex
- the index of the last element (exclusive) to be sorted.isAscending
- true for data sorted in increasing order.
IllegalArgumentException
- if fromIndex > toIndex
ArrayIndexOutOfBoundsException
- if fromIndex < 0
or
toIndex > a.length
public static int[] indices(double[] a, int fromIndex, int toIndex, boolean isAscending)
public static int[] indices(int[] a, int fromIndex, int toIndex, boolean isAscending)
public static void twoArrays(float[] x, float[] y, int fromIndex, int toIndex, boolean isAscending)
x
and y
arrays according to
x
and going from fromIndex
(inclusive) to toIndex
(exclusive)
in ascending or descending order.
The algorithm used to obtain these indices is a modified version of the tuned quicksort proposed by Jon L. Bentley and M. Douglas McIlroy's "Engineering a Sort Function", Software-Practice and Experience, Vol. 23(11) P. 1249-1265 (November 1993) (program 7 of the paper; currently used in the Arrays.sort() method to sort arrays).
It is a modified version in the sense that two arrays are sorted according to the first
array. At the end of the method, the section of both arrays going from
fromIndex
(inclusive) to toIndex
(exclusive) are sorted according
to the first array's order. Use a copy of both arrays if you want to preserve the natural order of
the original arrays.
x
- the array to sort.y
- the second array, to sort according to x
.fromIndex
- the index of the first element (inclusive) to be
sorted.toIndex
- the index of the last element (exclusive) to be sorted.isAscending
- true for data sorted in increasing order.
IllegalArgumentException
- if fromIndex > toIndex
ArrayIndexOutOfBoundsException
- if fromIndex < 0
or
toIndex > a.length
Arrays.sort(float[])
public static void twoArrays(double[] x, double[] y, int fromIndex, int toIndex, boolean isAscending)
public static void twoArrays(int[] x, int[] y, int fromIndex, int toIndex, boolean isAscending)
|
||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |