Package com.irurueta.sorting

Class Sorter<T>

java.lang.Object

com.irurueta.sorting.Sorter<T>

Type Parameters:

T - Type of instances being sorted.

Direct Known Subclasses:

HeapsortSorter, QuicksortSorter, ShellSorter, StraightInsertionSorter

public abstract class Sorter<T>
extends Object

Sorts instances of type T in provided arrays using any of the available methods.

Field Summary

Fields

Modifier and Type	Field	Description
static final SortingMethod	DEFAULT_SORTING_METHOD	Default method to be used for sorting if none is provided.

Constructor Summary

Constructors

Constructor	Description
Sorter()

Method Summary

Modifier and Type	Method	Description
static <T> Sorter<T>	create()	Creates a Sorter instance using DEFAULT_SORTING_METHOD.
static <T> Sorter<T>	create(SortingMethod method)	Creates a Sorter instance using provided sorting method.
protected int[]	getInitialIndicesVector(int length)	Returns a new array containing original indices ordered from 0 to length-1.
abstract SortingMethod	getMethod()	Returns sorting method of an implementation of this class.
double	median(double[] array)	Computes median of provided array Median is computed by selecting the length / 2 element, hence provided array is modified upon execution of this method containing sorted element at location length / 2, smaller unsorted elements at array[0] ...
double	median(double[] array, int fromIndex, int toIndex)	Computes median of provided array.
float	median(float[] array)	Computes median of provided array.
float	median(float[] array, int fromIndex, int toIndex)	Computes median of provided array.
int	median(int[] array)	Computes median of provided array.
int	median(int[] array, int fromIndex, int toIndex)	Computes median of provided array.
long	median(long[] array)	Computes median of provided array.
long	median(long[] array, int fromIndex, int toIndex)	Computes median of provided array.
T	median(Comparable<T>[] array)	Computes median of provided array Median is computed by selecting the length / 2 element, hence provided array is modified upon execution of this method containing sorted element at location length / 2, smaller unsorted elements at array[0] ...
T	median(Comparable<T>[] array, int fromIndex, int toIndex)	Computes median of provided array of Comparable Median is computed by selecting the ((toIndex - fromIndex) + fromIndex) / 2 element, hence provided array is modified upon execution of this method containing sorted element at location ((toIndex - fromIndex) + fromIndex) / 2, smaller unsorted elements at array[fromIndex] ...
T	median(T[] array, int fromIndex, int toIndex, ComparatorAndAverager<T> comparator)	Computes median of provided array.
T	median(T[] array, ComparatorAndAverager<T> comparator)	Computes median of provided array Median is computed by selecting the length / 2 element, hence provided array is modified upon execution of this method containing sorted element at location length / 2, smaller unsorted elements at array[0] ...
double	select(int k, double[] array)	Returns the k-th sorted element in provided array.
double	select(int k, double[] array, int fromIndex, int toIndex)	Returns the k-th sorted element in provided array of Comparable starting at fromIndex and finishing at toIndex, elements outside this range are ignored.
float	select(int k, float[] array)	Returns the k-th sorted element in provided array.
float	select(int k, float[] array, int fromIndex, int toIndex)	Returns the k-th sorted element in provided array of Comparable starting at fromIndex and finishing at toIndex, elements outside this range are ignored.
int	select(int k, int[] array)	Returns the k-th sorted element in provided array.
int	select(int k, int[] array, int fromIndex, int toIndex)	Returns the k-th sorted element in provided array of Comparable starting at fromIndex and finishing at toIndex, elements outside this range are ignored.
long	select(int k, long[] array)	Returns the k-th sorted element in provided array.
long	select(int k, long[] array, int fromIndex, int toIndex)	Returns the k-th sorted element in provided array of Comparable starting at fromIndex and finishing at toIndex, elements outside this range are ignored.
T	select(int k, Comparable<T>[] array)	Returns the k-th sorted element in provided array of Comparable.
T	select(int k, Comparable<T>[] array, int fromIndex, int toIndex)	Returns the k-th sorted element in provided array of Comparable starting at fromIndex and finishing at toIndex, elements outside this range are ignored.
T	select(int k, T[] array, int fromIndex, int toIndex, Comparator<T> comparator)	Returns the k-th sorted element in provided array of Comparable starting at fromIndex and finishing at toIndex, elements outside this range are ignored.
T	select(int k, T[] array, Comparator<T> comparator)	Returns the k-th sorted element in provided array.
void	sort(double[] array)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
abstract void	sort(double[] array, int fromIndex, int toIndex)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
void	sort(float[] array)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
abstract void	sort(float[] array, int fromIndex, int toIndex)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
void	sort(int[] array)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
abstract void	sort(int[] array, int fromIndex, int toIndex)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
void	sort(long[] array)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
abstract void	sort(long[] array, int fromIndex, int toIndex)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
void	sort(Comparable<T>[] array)	Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i.
void	sort(Comparable<T>[] array, int fromIndex, int toIndex)	Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i.
abstract void	sort(T[] array, int fromIndex, int toIndex, Comparator<T> comparator)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
void	sort(T[] array, Comparator<T> comparator)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
int[]	sortWithIndices(double[] array)	Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i.
abstract int[]	sortWithIndices(double[] array, int fromIndex, int toIndex)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
int[]	sortWithIndices(float[] array)	Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i.
abstract int[]	sortWithIndices(float[] array, int fromIndex, int toIndex)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
int[]	sortWithIndices(int[] array)	Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i.
abstract int[]	sortWithIndices(int[] array, int fromIndex, int toIndex)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
int[]	sortWithIndices(long[] array)	Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i.
abstract int[]	sortWithIndices(long[] array, int fromIndex, int toIndex)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
int[]	sortWithIndices(Comparable<T>[] array)	Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i.
int[]	sortWithIndices(Comparable<T>[] array, int fromIndex, int toIndex)	Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i.
abstract int[]	sortWithIndices(T[] array, int fromIndex, int toIndex, Comparator<T> comparator)	Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i.
int[]	sortWithIndices(T[] array, Comparator<T> comparator)	Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i.
protected void	swap(double[] arr, int posA, int posB)	Swaps values in array at locations posA and posB.
protected void	swap(float[] arr, int posA, int posB)	Swaps values in array at locations posA and posB.
protected void	swap(int[] arr, int posA, int posB)	Swaps values in array at locations posA and posB.
protected void	swap(long[] arr, int posA, int posB)	Swaps values in array at locations posA and posB.
protected void	swap(T[] arr, int posA, int posB)	Swaps values in array at locations posA and posB.

Methods inherited from class java.lang.Object

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

Field Details

DEFAULT_SORTING_METHOD

public static final SortingMethod DEFAULT_SORTING_METHOD

Default method to be used for sorting if none is provided.

Constructor Details

Sorter

public Sorter()

Method Details

sort

public abstract void sort(T[] array,
 int fromIndex,
 int toIndex,
 Comparator<T> comparator)
                   throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

comparator - Determines whether an element is greater or lower than another one.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sortWithIndices

public abstract int[] sortWithIndices(T[] array,
 int fromIndex,
 int toIndex,
 Comparator<T> comparator)
                               throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

comparator - Determines whether an element is greater or lower than another one.

Returns:

Array containing original location of elements that have been sorted. Only elements between fromIndex (inclusive) and toIndex (exclusive) are modified, the remaining ones are kept in natural order.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sort

public abstract void sort(double[] array,
 int fromIndex,
 int toIndex)
                   throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sortWithIndices

public abstract int[] sortWithIndices(double[] array,
 int fromIndex,
 int toIndex)
                               throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

Array containing original location of elements that have been sorted. Only elements between fromIndex (inclusive) and toIndex (exclusive) are modified, the remaining ones are kept in natural order.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sort

public abstract void sort(float[] array,
 int fromIndex,
 int toIndex)
                   throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sortWithIndices

public abstract int[] sortWithIndices(float[] array,
 int fromIndex,
 int toIndex)
                               throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

Array containing original location of elements that have been sorted. Only elements between fromIndex (inclusive) and toIndex (exclusive) are modified, the remaining ones are kept in natural order.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sort

public abstract void sort(int[] array,
 int fromIndex,
 int toIndex)
                   throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sortWithIndices

public abstract int[] sortWithIndices(int[] array,
 int fromIndex,
 int toIndex)
                               throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

Array containing original location of elements that have been sorted. Only elements between fromIndex (inclusive) and toIndex (exclusive) are modified, the remaining ones are kept in natural order.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sort

public abstract void sort(long[] array,
 int fromIndex,
 int toIndex)
                   throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sortWithIndices

public abstract int[] sortWithIndices(long[] array,
 int fromIndex,
 int toIndex)
                               throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

Array containing original location of elements that have been sorted. Only elements between fromIndex (inclusive) and toIndex (exclusive) are modified, the remaining ones are kept in natural order.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sort

public void sort(Comparable<T>[] array,
 int fromIndex,
 int toIndex)
          throws SortingException

Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sort

public void sort(Comparable<T>[] array)
          throws SortingException

Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.

Parameters:

array - Array to be sorted. After execution of this method all elements in array are modified so that they are on ascending order.

Throws:

SortingException - If for some reason sorting fails.

sort

public void sort(T[] array,
 Comparator<T> comparator)
          throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.

Parameters:

array - Array to be sorted. After execution of this method all elements in array are modified so that they are on ascending order.

comparator - Determines whether an element is greater or lower than another one.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sort

public void sort(double[] array)
          throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.

Parameters:

array - Array to be sorted. After execution of this method all elements in array are modified so that they are on ascending order.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sort

public void sort(float[] array)
          throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.

Parameters:

array - Array to be sorted. After execution of this method all elements in array are modified so that they are on ascending order.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sort

public void sort(int[] array)
          throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.

Parameters:

array - Array to be sorted. After execution of this method all elements in array are modified so that they are on ascending order.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sort

public void sort(long[] array)
          throws SortingException

Sorts provided array in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered.

Parameters:

array - Array to be sorted. After execution of this method all elements in array are modified so that they are on ascending order.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sortWithIndices

public int[] sortWithIndices(Comparable<T>[] array,
 int fromIndex,
 int toIndex)
                      throws SortingException

Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.

Parameters:

array - Array to be sorted. After execution of this method elements in array between fromIndex (inclusive) and toIndex (exclusive) are modified so that they are on ascending order.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

Array containing original location of elements that have been sorted. Only elements between fromIndex (inclusive) and toIndex (exclusive) are modified, the remaining ones are kept in natural order.

Throws:

SortingException - If for some reason sorting fails.

IllegalArgumentException - If fromIndex > toIndex.

ArrayIndexOutOfBoundsException - if fromIndex < 0 or toIndex > array.length.

sortWithIndices

public int[] sortWithIndices(Comparable<T>[] array)
                      throws SortingException

Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.

Parameters:

array - Array to be sorted. After execution of this method all elements in array are modified so that they are on ascending order.

Returns:

Array containing original location of elements that have been sorted.

Throws:

SortingException - If for some reason sorting fails.

sortWithIndices

public int[] sortWithIndices(T[] array,
 Comparator<T> comparator)
                      throws SortingException

Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.

Parameters:

array - Array to be sorted. After execution of this method all elements in array are modified so that they are on ascending order.

comparator - Determines whether an element is greater or lower than another one.

Returns:

Array containing original location of elements that have been sorted.

Throws:

SortingException - If for some reason sorting fails.

sortWithIndices

public int[] sortWithIndices(double[] array)
                      throws SortingException

Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.

Parameters:

array - Array to be sorted. After execution of this method all elements in array are modified so that they are on ascending order.

Returns:

Array containing original location of elements that have been sorted.

Throws:

SortingException - If for some reason sorting fails.

sortWithIndices

public int[] sortWithIndices(float[] array)
                      throws SortingException

Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.

Parameters:

array - Array to be sorted. After execution of this method all elements in array are modified so that they are on ascending order.

Returns:

Array containing original location of elements that have been sorted.

Throws:

SortingException - If for some reason sorting fails.

sortWithIndices

public int[] sortWithIndices(int[] array)
                      throws SortingException

Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.

Parameters:

array - Array to be sorted. After execution of this method all elements in array are modified so that they are on ascending order.

Returns:

Array containing original location of elements that have been sorted.

Throws:

SortingException - If for some reason sorting fails.

sortWithIndices

public int[] sortWithIndices(long[] array)
                      throws SortingException

Sorts provided array of Comparable in ascending order so that array[i - 1] < array[i] for any valid i. This method modifies provided array so that after execution of this method array elements are ordered. An array containing the original indices where elements were located is returned so that other arrays or collections can be kept in the same order.

Parameters:

array - Array to be sorted. After execution of this method all elements in array are modified so that they are on ascending order.

Returns:

Array containing original location of elements that have been sorted.

Throws:

SortingException - If for some reason sorting fails.

select

public T select(int k,
 Comparable<T>[] array)

Returns the k-th sorted element in provided array of Comparable. Selecting an element is usually faster than sorting the whole array, and for that reason, when only a few sorted elements are required, this method should be used instead of sort. Because array is passed by reference, after executing this method array is modified so that in k location it contains the k-th sorted elements and on locations array[0] ... array[k-1] contains unsorted elements smaller than sorted element array[k], and on locations array[k+1] ... array[length-1] contains unsorted elements greater than sorted element array[k].

Parameters:

k - Position of sorted element to be retrieved.

array - Array to be used for retrieving k-th sorted element. Provided array is passed by reference and modified upon execution of this method so that k-th location contains k-th sorted element, and array[0] ... array[k-1] contains unsorted elements smaller than sorted element array[k] and array[k+1] ... array[length-1] contains elements greater than sorted element array[k]

Returns:

The k-th sorted element in provided array

Throws:

IllegalArgumentException - if k < array.length

select

public T select(int k,
 Comparable<T>[] array,
 int fromIndex,
 int toIndex)

Returns the k-th sorted element in provided array of Comparable starting at fromIndex and finishing at toIndex, elements outside this range are ignored. Selecting an element is usually faster than sorting the whole array, and for that reason, when only a few sorted elements are required, this method should be used instead of sort. Because array is passed by reference, after executing this method array is modified so that in k location it contains the k-th sorted elements and on locations array[fromIndex] ... array[k-1 + fromIndex] contains unsorted elements smaller than sorted element array[k + fromIndex], and on locations array[k+1 + fromIndex] ... array[toIndex-1] contains unsorted elements greater than sorted element array[k + fromIndex].

Parameters:

k - Position of sorted element to be retrieved.

array - Array to be used for retrieving k-th sorted element. Provided array is passed by reference and modified upon execution of this method so that k-th location contains k-th sorted element, and array[fromIndex] ... array[k-1 + fromIndex] contains unsorted elements smaller than sorted element array[k + fromIndex] and array[k+1 + fromIndex] ... array[toIndex-1] contains elements greater than sorted element array[k].

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

The k-th sorted element in provided array.

Throws:

IllegalArgumentException - if k < (toIndex - fromIndex) or fromIndex < toIndex.

ArrayIndexOutOfBoundsException - if fromIndex or toIndex are outside array boundaries.

select

public T select(int k,
 T[] array,
 Comparator<T> comparator)

Returns the k-th sorted element in provided array. Selecting an element is usually faster than sorting the whole array, and for that reason, when only a few sorted elements are required, this method should be used instead of sort. Because array is passed by reference, after executing this method array is modified so that in k location it contains the k-th sorted elements and on locations array[0] ... array[k-1] contains unsorted elements smaller than sorted element array[k], and on locations array[k+1] ... array[length-1] contains unsorted elements greater than sorted element array[k].

Parameters:

k - Position of sorted element to be retrieved.

array - Array to be used for retrieving k-th sorted element. Provided array is passed by reference and modified upon execution of this method so that k-th location contains k-th sorted element, and array[0] ... array[k-1] contains unsorted elements smaller than sorted element array[k] and array[k+1] ... array[length-1] contains elements greater than sorted element array[k].

comparator - Determines whether an element is greater or lower than another one.

Returns:

The k-th sorted element in provided array.

Throws:

IllegalArgumentException - k < array.length.

select

public double select(int k,
 double[] array)

Returns the k-th sorted element in provided array. Selecting an element is usually faster than sorting the whole array, and for that reason, when only a few sorted elements are required, this method should be used instead of sort. Because array is passed by reference, after executing this method array is modified so that in k location it contains the k-th sorted elements and on locations array[0] ... array[k-1] contains unsorted elements smaller than sorted element array[k], and on locations array[k+1] ... array[length-1] contains unsorted elements greater than sorted element array[k].

Parameters:

k - Position of sorted element to be retrieved.

array - Array to be used for retrieving k-th sorted element. Provided array is passed by reference and modified upon execution of this method so that k-th location contains k-th sorted element, and array[0] ... array[k-1] contains unsorted elements smaller than sorted element array[k] and array[k+1] ... array[length-1] contains elements greater than sorted element array[k].

Returns:

The k-th sorted element in provided array.

Throws:

IllegalArgumentException - k < array.length.

select

public float select(int k,
 float[] array)

Returns the k-th sorted element in provided array. Selecting an element is usually faster than sorting the whole array, and for that reason, when only a few sorted elements are required, this method should be used instead of sort. Because array is passed by reference, after executing this method array is modified so that in k location it contains the k-th sorted elements and on locations array[0] ... array[k-1] contains unsorted elements smaller than sorted element array[k], and on locations array[k+1] ... array[length-1] contains unsorted elements greater than sorted element array[k].

Parameters:

k - Position of sorted element to be retrieved.

array - Array to be used for retrieving k-th sorted element. Provided array is passed by reference and modified upon execution of this method so that k-th location contains k-th sorted element, and array[0] ... array[k-1] contains unsorted elements smaller than sorted element array[k] and array[k+1] ... array[length-1] contains elements greater than sorted element array[k].

Returns:

The k-th sorted element in provided array.

Throws:

IllegalArgumentException - k < array.length.

select

public int select(int k,
 int[] array)

Returns the k-th sorted element in provided array. Selecting an element is usually faster than sorting the whole array, and for that reason, when only a few sorted elements are required, this method should be used instead of sort. Because array is passed by reference, after executing this method array is modified so that in k location it contains the k-th sorted elements and on locations array[0] ... array[k-1] contains unsorted elements smaller than sorted element array[k], and on locations array[k+1] ... array[length-1] contains unsorted elements greater than sorted element array[k].

Parameters:

k - Position of sorted element to be retrieved.

array - Array to be used for retrieving k-th sorted element. Provided array is passed by reference and modified upon execution of this method so that k-th location contains k-th sorted element, and array[0] ... array[k-1] contains unsorted elements smaller than sorted element array[k] and array[k+1] ... array[length-1] contains elements greater than sorted element array[k].

Returns:

The k-th sorted element in provided array.

Throws:

IllegalArgumentException - k < array.length.

select

public long select(int k,
 long[] array)

Returns the k-th sorted element in provided array. Selecting an element is usually faster than sorting the whole array, and for that reason, when only a few sorted elements are required, this method should be used instead of sort. Because array is passed by reference, after executing this method array is modified so that in k location it contains the k-th sorted elements and on locations array[0] ... array[k-1] contains unsorted elements smaller than sorted element array[k], and on locations array[k+1] ... array[length-1] contains unsorted elements greater than sorted element array[k].

Parameters:

k - Position of sorted element to be retrieved.

array - Array to be used for retrieving k-th sorted element. Provided array is passed by reference and modified upon execution of this method so that k-th location contains k-th sorted element, and array[0] ... array[k-1] contains unsorted elements smaller than sorted element array[k] and array[k+1] ... array[length-1] contains elements greater than sorted element array[k].

Returns:

The k-th sorted element in provided array.

Throws:

IllegalArgumentException - k < array.length.

select

public T select(int k,
 T[] array,
 int fromIndex,
 int toIndex,
 Comparator<T> comparator)

Returns the k-th sorted element in provided array of Comparable starting at fromIndex and finishing at toIndex, elements outside this range are ignored. Selecting an element is usually faster than sorting the whole array, and for that reason, when only a few sorted elements are required, this method should be used instead of sort. Because array is passed by reference, after executing this method array is modified so that in k location it contains the k-th sorted elements and on locations array[fromIndex] ... array[k-1 + fromIndex] contains unsorted elements smaller than sorted element array[k + fromIndex], and on locations array[k+1 + fromIndex] ... array[toIndex-1] contains unsorted elements greater than sorted element array[k + fromIndex]

Parameters:

k - Position of sorted element to be retrieved.

array - Array to be used for retrieving k-th sorted element. Provided array is passed by reference and modified upon execution of this method so that k-th location contains k-th sorted element, and array[fromIndex] ... array[k-1 + fromIndex] contains unsorted elements smaller than sorted element array[k + fromIndex] and array[k+1 + fromIndex] ... array[toIndex-1] contains elements greater than sorted element array[k].

comparator - Determines whether an element is greater or lower than another one.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

The k-th sorted element in provided array.

Throws:

IllegalArgumentException - if k < (toIndex - fromIndex) or fromIndex < toIndex.

ArrayIndexOutOfBoundsException - if fromIndex or toIndex are outside array boundaries.

select

public double select(int k,
 double[] array,
 int fromIndex,
 int toIndex)

Returns the k-th sorted element in provided array of Comparable starting at fromIndex and finishing at toIndex, elements outside this range are ignored. Selecting an element is usually faster than sorting the whole array, and for that reason, when only a few sorted elements are required, this method should be used instead of sort. Because array is passed by reference, after executing this method array is modified so that in k location it contains the k-th sorted elements and on locations array[fromIndex] ... array[k-1 + fromIndex] contains unsorted elements smaller than sorted element array[k + fromIndex], and on locations array[k+1 + fromIndex] ... array[toIndex-1] contains unsorted elements greater than sorted element array[k + fromIndex].

Parameters:

k - Position of sorted element to be retrieved.

array - Array to be used for retrieving k-th sorted element. Provided array is passed by reference and modified upon execution of this method so that k-th location contains k-th sorted element, and array[fromIndex] ... array[k-1 + fromIndex] contains unsorted elements smaller than sorted element array[k + fromIndex] and array[k+1 + fromIndex] ... array[toIndex-1] contains elements greater than sorted element array[k].

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

The k-th sorted element in provided array.

Throws:

IllegalArgumentException - if k < (toIndex - fromIndex) or fromIndex < toIndex.

ArrayIndexOutOfBoundsException - if fromIndex or toIndex are outside array boundaries.

select

public float select(int k,
 float[] array,
 int fromIndex,
 int toIndex)

Returns the k-th sorted element in provided array of Comparable starting at fromIndex and finishing at toIndex, elements outside this range are ignored. Selecting an element is usually faster than sorting the whole array, and for that reason, when only a few sorted elements are required, this method should be used instead of sort. Because array is passed by reference, after executing this method array is modified so that in k location it contains the k-th sorted elements and on locations array[fromIndex] ... array[k-1 + fromIndex] contains unsorted elements smaller than sorted element array[k + fromIndex], and on locations array[k+1 + fromIndex] ... array[toIndex-1] contains unsorted elements greater than sorted element array[k + fromIndex].

Parameters:

k - Position of sorted element to be retrieved.

array - Array to be used for retrieving k-th sorted element. Provided array is passed by reference and modified upon execution of this method so that k-th location contains k-th sorted element, and array[fromIndex] ... array[k-1 + fromIndex] contains unsorted elements smaller than sorted element array[k + fromIndex] and array[k+1 + fromIndex] ... array[toIndex-1] contains elements greater than sorted element array[k].

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

The k-th sorted element in provided array.

Throws:

IllegalArgumentException - if k < (toIndex - fromIndex) or fromIndex < toIndex.

ArrayIndexOutOfBoundsException - if fromIndex or toIndex are outside array boundaries.

select

public int select(int k,
 int[] array,
 int fromIndex,
 int toIndex)

Returns the k-th sorted element in provided array of Comparable starting at fromIndex and finishing at toIndex, elements outside this range are ignored. Selecting an element is usually faster than sorting the whole array, and for that reason, when only a few sorted elements are required, this method should be used instead of sort. Because array is passed by reference, after executing this method array is modified so that in k location it contains the k-th sorted elements and on locations array[fromIndex] ... array[k-1 + fromIndex] contains unsorted elements smaller than sorted element array[k + fromIndex], and on locations array[k+1 + fromIndex] ... array[toIndex-1] contains unsorted elements greater than sorted element array[k + fromIndex].

Parameters:

k - Position of sorted element to be retrieved.

array - Array to be used for retrieving k-th sorted element. Provided array is passed by reference and modified upon execution of this method so that k-th location contains k-th sorted element, and array[fromIndex] ... array[k-1 + fromIndex] contains unsorted elements smaller than sorted element array[k + fromIndex] and array[k+1 + fromIndex] ... array[toIndex-1] contains elements greater than sorted element array[k].

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

The k-th sorted element in provided array.

Throws:

IllegalArgumentException - if k < (toIndex - fromIndex) or fromIndex < toIndex.

ArrayIndexOutOfBoundsException - if fromIndex or toIndex are outside array boundaries.

select

public long select(int k,
 long[] array,
 int fromIndex,
 int toIndex)

Returns the k-th sorted element in provided array of Comparable starting at fromIndex and finishing at toIndex, elements outside this range are ignored. Selecting an element is usually faster than sorting the whole array, and for that reason, when only a few sorted elements are required, this method should be used instead of sort. Because array is passed by reference, after executing this method array is modified so that in k location it contains the k-th sorted elements and on locations array[fromIndex] ... array[k-1 + fromIndex] contains unsorted elements smaller than sorted element array[k + fromIndex], and on locations array[k+1 + fromIndex] ... array[toIndex-1] contains unsorted elements greater than sorted element array[k + fromIndex].

Parameters:

k - Position of sorted element to be retrieved.

array - Array to be used for retrieving k-th sorted element. Provided array is passed by reference and modified upon execution of this method so that k-th location contains k-th sorted element, and array[fromIndex] ... array[k-1 + fromIndex] contains unsorted elements smaller than sorted element array[k + fromIndex] and array[k+1 + fromIndex] ... array[toIndex-1] contains elements greater than sorted element array[k].

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

The k-th sorted element in provided array.

Throws:

IllegalArgumentException - if k < (toIndex - fromIndex) or fromIndex < toIndex.

ArrayIndexOutOfBoundsException - if fromIndex or toIndex are outside array boundaries.

median

public T median(Comparable<T>[] array)

Computes median of provided array Median is computed by selecting the length / 2 element, hence provided array is modified upon execution of this method containing sorted element at location length / 2, smaller unsorted elements at array[0] ... array[length / 2 - 1], and greater unsorted elements at array[length / 2 + 1] ... array[length - 1].

Parameters:

array - Array to be used for computation of median. This array is modified after execution of this method.

Returns:

Median of provided array.

median

public T median(Comparable<T>[] array,
 int fromIndex,
 int toIndex)

Computes median of provided array of Comparable Median is computed by selecting the ((toIndex - fromIndex) + fromIndex) / 2 element, hence provided array is modified upon execution of this method containing sorted element at location ((toIndex - fromIndex) + fromIndex) / 2, smaller unsorted elements at array[fromIndex] ... array[((toIndex - fromIndex) + fromIndex) / 2 - 1], and greater unsorted elements at array[((toIndex - fromIndex) + fromIndex) / 2 + 1] ... array[toIndex - 1].

Parameters:

array - Array to be used for computation of median. This array is modified after execution of this method.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

Median of provided array.

Throws:

IllegalArgumentException - if k < (toIndex - fromIndex) or fromIndex < toIndex.

ArrayIndexOutOfBoundsException - if fromIndex or toIndex are outside array boundaries.

median

public T median(T[] array,
 ComparatorAndAverager<T> comparator)

Computes median of provided array Median is computed by selecting the length / 2 element, hence provided array is modified upon execution of this method containing sorted element at location length / 2, smaller unsorted elements at array[0] ... array[length / 2 - 1], and greater unsorted elements at array[length / 2 + 1] ... array[length - 1].

Parameters:

array - Array to be used for computation of median. This array is modified after execution of this method.

comparator - Determines whether an element is greater or lower than another one and also is capable of computing the average between two T instances.

Returns:

Median of provided array.

median

public double median(double[] array)

Computes median of provided array Median is computed by selecting the length / 2 element, hence provided array is modified upon execution of this method containing sorted element at location length / 2, smaller unsorted elements at array[0] ... array[length / 2 - 1], and greater unsorted elements at array[length / 2 + 1] ... array[length - 1].

Parameters:

array - Array to be used for computation of median. This array is modified after execution of this method.

Returns:

Median of provided array.

median

public float median(float[] array)

Computes median of provided array. Median is computed by selecting the length / 2 element, hence provided array is modified upon execution of this method containing sorted element at location length / 2, smaller unsorted elements at array[0] ... array[length / 2 - 1], and greater unsorted elements at array[length / 2 + 1] ... array[length - 1].

Parameters:

array - Array to be used for computation of median. This array is modified after execution of this method.

Returns:

Median of provided array.

median

public int median(int[] array)

Computes median of provided array. Median is computed by selecting the length / 2 element, hence provided array is modified upon execution of this method containing sorted element at location length / 2, smaller unsorted elements at array[0] ... array[length / 2 - 1], and greater unsorted elements at array[length / 2 + 1] ... array[length - 1].

Parameters:

array - Array to be used for computation of median. This array is modified after execution of this method.

Returns:

Median of provided array.

median

public long median(long[] array)

Computes median of provided array. Median is computed by selecting the length / 2 element, hence provided array is modified upon execution of this method containing sorted element at location length / 2, smaller unsorted elements at array[0] ... array[length / 2 - 1], and greater unsorted elements at array[length / 2 + 1] ... array[length - 1].

Parameters:

array - Array to be used for computation of median. This array is modified after execution of this method.

Returns:

Median of provided array.

median

public T median(T[] array,
 int fromIndex,
 int toIndex,
 ComparatorAndAverager<T> comparator)

Computes median of provided array. Median is computed by selecting the ((toIndex - fromIndex) + fromIndex) / 2 element, hence provided array is modified upon execution of this method containing sorted element at location ((toIndex - fromIndex) + fromIndex) / 2, smaller unsorted elements at array[fromIndex] ... array[((toIndex - fromIndex) + fromIndex) / 2 - 1], and greater unsorted elements at array[((toIndex - fromIndex) + fromIndex) / 2 + 1] ... array[toIndex - 1].

Parameters:

array - Array to be used for computation of median. This array is modified after execution of this method.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

comparator - Determines whether an element is greater or lower than another one and also is capable of computing the average between two T instances.

Returns:

Median of provided array.

Throws:

IllegalArgumentException - if fromIndex is greater than toIndex.

ArrayIndexOutOfBoundsException - if either fromIndex or toIndex are out of bounds.

median

public double median(double[] array,
 int fromIndex,
 int toIndex)

Computes median of provided array. Median is computed by selecting the ((toIndex - fromIndex) + fromIndex) / 2 element, hence provided array is modified upon execution of this method containing sorted element at location ((toIndex - fromIndex) + fromIndex) / 2, smaller unsorted elements at array[fromIndex] ... array[((toIndex - fromIndex) + fromIndex) / 2 - 1], and greater unsorted elements at array[((toIndex - fromIndex) + fromIndex) / 2 + 1] ... array[toIndex - 1].

Parameters:

array - Array to be used for computation of median. This array is modified after execution of this method.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

Median of provided array.

Throws:

IllegalArgumentException - if fromIndex is greater than toIndex.

ArrayIndexOutOfBoundsException - if either fromIndex or toIndex are out of bounds.

median

public float median(float[] array,
 int fromIndex,
 int toIndex)

Computes median of provided array. Median is computed by selecting the ((toIndex - fromIndex) + fromIndex) / 2 element, hence provided array is modified upon execution of this method containing sorted element at location ((toIndex - fromIndex) + fromIndex) / 2, smaller unsorted elements at array[fromIndex] ... array[((toIndex - fromIndex) + fromIndex) / 2 - 1], and greater unsorted elements at array[((toIndex - fromIndex) + fromIndex) / 2 + 1] ... array[toIndex - 1].

Parameters:

array - Array to be used for computation of median. This array is modified after execution of this method.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

Median of provided array.

Throws:

IllegalArgumentException - if fromIndex is greater than toIndex.

ArrayIndexOutOfBoundsException - if either fromIndex or toIndex are out of bounds.

median

public int median(int[] array,
 int fromIndex,
 int toIndex)

Computes median of provided array. Median is computed by selecting the ((toIndex - fromIndex) + fromIndex) / 2 element, hence provided array is modified upon execution of this method containing sorted element at location ((toIndex - fromIndex) + fromIndex) / 2, smaller unsorted elements at array[fromIndex] ... array[((toIndex - fromIndex) + fromIndex) / 2 - 1], and greater unsorted elements at array[((toIndex - fromIndex) + fromIndex) / 2 + 1] ... array[toIndex - 1].

Parameters:

array - Array to be used for computation of median. This array is modified after execution of this method.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

Median of provided array.

Throws:

IllegalArgumentException - if fromIndex is greater than toIndex.

ArrayIndexOutOfBoundsException - if either fromIndex or toIndex are out of bounds.

median

public long median(long[] array,
 int fromIndex,
 int toIndex)

Computes median of provided array. Median is computed by selecting the ((toIndex - fromIndex) + fromIndex) / 2 element, hence provided array is modified upon execution of this method containing sorted element at location ((toIndex - fromIndex) + fromIndex) / 2, smaller unsorted elements at array[fromIndex] ... array[((toIndex - fromIndex) + fromIndex) / 2 - 1], and greater unsorted elements at array[((toIndex - fromIndex) + fromIndex) / 2 + 1] ... array[toIndex - 1].

Parameters:

array - Array to be used for computation of median. This array is modified after execution of this method.

fromIndex - Index were sorting starts (inclusive).

toIndex - Index were sorting stops (exclusive).

Returns:

Median of provided array.

Throws:

IllegalArgumentException - if fromIndex is greater than toIndex.

ArrayIndexOutOfBoundsException - if either fromIndex or toIndex are out of bounds.

getMethod

public abstract SortingMethod getMethod()

Returns sorting method of an implementation of this class.

Returns:

Sorting method.

create

public static <T> Sorter<T> create()

Creates a Sorter instance using DEFAULT_SORTING_METHOD.

Returns:

A sorter instance.

create

public static <T> Sorter<T> create(SortingMethod method)

Creates a Sorter instance using provided sorting method.

Parameters:

method - Method to be used for sorting.

Returns:

A sorter instance.

getInitialIndicesVector

protected int[] getInitialIndicesVector(int length)

Returns a new array containing original indices ordered from 0 to length-1.

Parameters:

length - length of returned array.

Returns:

Array with indices in natural order.

swap

protected void swap(T[] arr,
 int posA,
 int posB)

Swaps values in array at locations posA and posB.

Parameters:

arr - array where values are swapped.

posA - Location to be swapped.

posB - Location to be swapped.

swap

protected void swap(double[] arr,
 int posA,
 int posB)

Swaps values in array at locations posA and posB.

Parameters:

arr - array where values are swapped.

posA - Location to be swapped.

posB - Location to be swapped.

swap

protected void swap(float[] arr,
 int posA,
 int posB)

Swaps values in array at locations posA and posB.

Parameters:

arr - array where values are swapped.

posA - Location to be swapped.

posB - Location to be swapped.

swap

protected void swap(int[] arr,
 int posA,
 int posB)

Swaps values in array at locations posA and posB.

Parameters:

arr - array where values are swapped.

posA - Location to be swapped.

posB - Location to be swapped.

swap

protected void swap(long[] arr,
 int posA,
 int posB)

Swaps values in array at locations posA and posB.

Parameters:

arr - array where values are swapped.

posA - Location to be swapped.

posB - Location to be swapped.