papaya
Class Sorting

java.lang.Object
  extended by papaya.Sorting

public final class Sorting
extends Object

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
X={1, 2, 3}, Y={2.0, 1.0, 3.0}, Z={8.0, 7.0, 6.0}
. To do this, we can use the indices corresponding to the elements of 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.

Author:
Adila Faruk

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

indices

public 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.

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.

Parameters:
a - the input array
isAscending - true for data sorted in increasing order.
Returns:
integar array of indices (with length=data.length) that can be used to sort the data from low to high or vice-versa.. * @throws IllegalArgumentException if fromIndex > toIndex
Throws:
ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length

indices

public static int[] indices(double[] a,
                            boolean isAscending)

indices

public static int[] indices(int[] a,
                            boolean isAscending)

indices

public 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.

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.

Parameters:
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.
Throws:
IllegalArgumentException - if fromIndex > toIndex
ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length

indices

public static int[] indices(double[] a,
                            int fromIndex,
                            int toIndex,
                            boolean isAscending)

indices

public static int[] indices(int[] a,
                            int fromIndex,
                            int toIndex,
                            boolean isAscending)

twoArrays

public 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.

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.

Parameters:
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.
Throws:
IllegalArgumentException - if fromIndex > toIndex
ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > a.length
See Also:
Arrays.sort(float[])

twoArrays

public static void twoArrays(double[] x,
                             double[] y,
                             int fromIndex,
                             int toIndex,
                             boolean isAscending)

twoArrays

public static void twoArrays(int[] x,
                             int[] y,
                             int fromIndex,
                             int toIndex,
                             boolean isAscending)


Processing library papaya by Adila Faruk. (C) 2014